题解：B4214 [常州市程序设计小能手 2022] 迷宫探险

_WsSB_aaa · 2025-04-05 19:22:09 · 题解

有一句话叫暴力出奇迹，我来分享一下我的暴力搜索做法。

实现过程

• 初始化：首先遍历地图，找出所有玩家的起始位置和计分器位置。将玩家起始位置信息加入队列，同时初始化距离数组和访问数组。
• BFS 过程：对每个玩家进行 BFS 搜索。每次从队列中取出一个位置，检查其四个相邻位置。如果相邻位置在地图范围内、不是障碍物且未被访问过，就更新该位置到玩家起始位置的距离，并将其加入队列。如果相邻位置是计分器位置，根据该位置的访问情况（是否第一次到达或是否与其他玩家同时到达）来决定玩家是否得分。
• 统计结果：BFS 搜索结束后，遍历每个玩家的得分情况，统计出得分最多的玩家得分以及所有玩家的总得分。

代码细节

• 数据定义 ： 使用二维字符数组 mp 存储地图信息。 定义结构体 Pos 表示位置，包含玩家编号、横坐标和纵坐标。
  三维数组 dist 记录每个玩家到地图上各点的距离。
  数组 res 记录每个玩家的得分。
  数组 vis 标记地图上的点是否被访问过。
• BFS 函数 ： 遍历地图找到所有玩家的起始位置，将其加入队列，并初始化距离数组。
  在 BFS 循环中，从队列中取出当前位置，向四个方向进行搜索。对于符合条件的相邻位置，更新距离并加入队列。如果到达计分器位置，根据访问数组判断是否得分。

AC Code：

#include <bits/stdc++.h>
const int MAXN = 200;
using namespace std;
char mp[MAXN][MAXN];

struct Pos {
    int id, x, y;
};

const int dx[4] = {1, -1, 0, 0};

const int dy[4] = {0, 0, -1, 1};
int dist[20][MAXN][MAXN], res[20], num, n, vis[MAXN][MAXN];

void bfs() {
    queue<Pos> que;

    // 遍历地图，找到所有起点（标记为 '@' 的点）
    for (int i = 1; i <= n; i++) {

        for (int j = 1; j <= n; j++) {

            if (mp[i][j] == '@') {
                num++;
                que.push({num, i, j});
                dist[num][i][j] = 1;
            }
        }
    }

    while (!que.empty()) {
        Pos cur = que.front();
        que.pop();
        int k = cur.id, x = cur.x, y = cur.y;

        // 遍历四个方向
        for (int i = 0; i < 4; i++) {

            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 1 && nx <= n && ny >= 1 && ny <= n && !dist[k][nx][ny] && mp[nx][ny] != '#') {
                dist[k][nx][ny] = dist[k][x][y] + 1;
                que.push({k, nx, ny});

                if (mp[nx][ny] == '$') {
                    if (vis[nx][ny] == 0 || vis[nx][ny] == dist[k][nx][ny]) {
                        // 标记该目标点已被访问
                        vis[nx][ny] = dist[k][nx][ny];
                        res[k]++;
                    }
                }
            }
        }
    }
}

signed main() {
    cin >> n;

    for (int i = 1; i <= n; i++) {

        for (int j = 1; j <= n; j++) {

            cin >> mp[i][j];
        }
    }

    bfs();
    int maxRes = 0, sumRes = 0;

    // 遍历所有起点，更新最大值和总数
    for (int i = 1; i <= num; i++) {

        maxRes = max(maxRes, res[i]);
        sumRes += res[i];
    }

    cout << maxRes << "\n" << sumRes << "\n";

    return 0;
}

本蒟蒻第一次写题解，点个赞再走吧。