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

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

实现过程

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

代码细节

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

AC Code：

CPP

#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;
}

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

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

文章操作

实现过程

代码细节

AC Code：

相关推荐

评论

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