题解：B4214 [常州市赛 2022] 迷宫探险

Ashankamiko · 2025-05-18 15:39:27 · 题解

题目简述

题意

给定一张 N \times N 的地图，地图只包含如下字符。

• 用 @ 表示其中一个玩家的起点。
• 用 # 表示墙，该处不可到达。
• 用 $ 表示计分器，在全局中只能使用一次，但是可以同时使用，优先到达的玩家可以使用，一起到达的要同时使用。
• 用 . 表示路，玩家可以移动到此处，且没有分数。

求玩家最高得到了几分以及所有玩家得到的总分。

思路 1

流程如下。

• 输入地图，如果 (x,y) 为 @，入队。
• 定义 dis 数组，用于储存到达 (x,y) 的最少步数（也可以说是离 (x,y) 最近的起点），并将 dis 的所有元素赋值为极大值。
• 取出队首，设 r 为到达 (x,y) 的最少步数。向四周扩展。如果是 $，并且 dis 仍然为极大值，令 dis_{tx,ty} \gets r + 1，入队时使分数加一；如果 dis 不是极大值，判断 r + 1 是否等于 dis_{tx,ty}，如果相等，仍然可以获得分数，否则没分。如果是 .，直接入队并且不改变分数。

  思路 2

  流程如下。

• 输入地图，定义数组 score，用于储存有多少个 $ 离 (x,y) 的最近的，也就是当前点扩展后的分数。定义 maxx 和 ans 用于储存最高分数和总分。
• 遍历地图，如果是 $，开始进行广搜。
• 取出队首，设 r 为到达 (x,y) 的最少步数。向四周扩展。如果 (tx,ty) 是 @，并且 dis_{tx,ty} 是极大值，令 score_{tx,ty} \gets score_{tx,ty} + 1，如果 r + 1 等于 dis_{tx,ty}，也令 score_{tx,ty} \gets score_{tx,ty} + 1，如果 (tx,ty) 是 . 入队。在扩展的过程中，需定义标记数组 vis，防止重复入队，不过需要注意的是，如果该点为 @，则需无视标记。
• 在广搜过程中，要不断更新 maxx，并在广搜结束更新 ans。

  struct node {
  int x, y; //坐标
  int r; //步数
  };
  char maps[105][105]; //地图
  int dis[105][105]; //最短路径
  int number[105][105]; //有几个$离当前点是最近的
  int score[105][105]; //分数
  queue<node> q;
  bool vis[105][105]; //标记数组

  在广搜的过程中，如果当前点为 @ 并且可以得到分数，参考以下代码。

  if (maps[ux][uy] == '@' && ur <= dis[x][y]) {
  dis[x][y] = ur, number[x][y]++, score[ux][uy]++, maxx = max(maxx, score[ux][uy]);
  continue;
  }

  最后输出 maxx 和 ans 就可以了。

  AC 代码

  
  #include <bits/stdc++.h>
  using namespace std;
  #define in cin
  #define out cout
  int n, dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}, maxx, cnt, ans; //基础定义
  struct node {
  int x, y, r;
  };
  char maps[105][105];
  int dis[105][105], number[105][105], score[105][105];
  queue<node> q;
  bool vis[105][105];

void bfs(int x, int y) { //广搜 memset(vis, 0, sizeof(vis)); q.push({x, y}), vis[x][y] = true; while (!q.empty()) { int ux = q.front().x, uy = q.front().y, ur = q.front().r; q.pop(); if (maps[ux][uy] == '@' && ur <= dis[x][y]) { dis[x][y] = ur, number[x][y]++, score[ux][uy]++, maxx = max(maxx, score[ux][uy]);//可以得到分数 continue; } for (int i = 0; i < 4; i++) { int tx = dx[i] + ux, ty = uy + dy[i]; if (tx >= 0 && ty >= 0 && tx < n && ty < n && maps[tx][ty] != '#' && !vis[tx][ty]) q.push({tx, ty, ur + 1}), vis[tx][ty] = true; } } ans += number[x][y]; } int main() { memset(dis, 0x3f, sizeof(dis)); //初始化 in >> n; for (int i = 0; i < n; i++) //输入地图 for (int j = 0; j < n; j++) in >> maps[i][j]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (maps[i][j] == '$') bfs(i, j); //对该点进行广搜 out << maxx << '\n' << ans; //输出答案 return 0; }