1672: 迷宫问题

解题思路:

主要考察BFS的思想，首先输入了一组迷宫的数据后，应该遍历一次记录起点和终点的位置。然后从起点所在的格子开始，朝着四个方向的相邻格子访问，如果那个格子不在界外（确保安全可以在最外围加一圈'#'代表墙壁）且未访问过，就将其设为访问过并入队，最后让队头出队，原来的格子就没有作用了（唯一作用是表示已访问防止重复访问），因为每次是朝四个方向走一格，所以到达终点时一定是最短的路径（其他的路线还在途中呢）。

另外，题目的要求是可能有多组数据，因此每轮BFS开始时一定要初始化迷宫，包括记录步数和记录是否已访问的数组。

注意事项:

我真傻，真的。我单知道题目的测试结果能通过，却没发现我初始化的代码是这么写的：

map[N][N] = { 0 };
step[N][N] = { 0 };
visit[N][N] = { 0 };

首先map是char型，visit是bool型，step是int型，这三个全写成0好像也没什么问题，不过还是建议用memset()初始化内存。其次，在cin >> N之前就能写出map[N][N]，我属于是纯纯的沙口了。

参考代码:

#include <iostream>
#include <cstring>
#include <queue>
#define MAX 100

using namespace std;

typedef pair<int, int> P;  // 用来表示状态坐标
char map[MAX][MAX];        // 地图
int step[MAX][MAX];        // 表示所走的步数
bool visit[MAX][MAX];      // 标记已经走过的格子
int dx[]= {0, 0, 1, -1};   // 四方向
int dy[]= {1, -1, 0, 0};   // 四方向
int sx, sy;                // 起点
int ex, ey;                // 终点
int flag = 0;              // 判断是否找到了终点
int N, M;                  // 题目要求输入

int BFS(); // 广度优先搜索
int main() {
	int num = 0; // 第一行数据
	cin >> num;

	while(num--) {
		// 初始化地图，奇妙的是不能直接map[N][N] = { 0 };
		memset(map, 0, sizeof(map));
		memset(step, 0, sizeof(step));
		memset(visit, 0, sizeof(visit));

		cin >> N >> M;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				cin >> map[i][j]; // 读输入
				if(map[i][j] == 'S') {
					sx = i;
					sy = j; // 存储起点坐标
				}
				if(map[i][j] == 'E') {
					ex = i;
					ey = j; // 存储终点坐标
				}
			}
		}

		cout << BFS() << endl;
		flag = 0; //初始化
	}
	return 0;
}
int BFS() {
	queue <P> que;       //申请队列
	que.push(P(sx, sy)); //把起点加入队列
	step[sx][sy] = 0;    //并且步数设置为0

	// 队列不为空就一直搜
	while(!que.empty()) {
		P p = que.front(); // 访问队首元素
		if(p.first == ex && p.second == ey) {
			flag = 1; // 找到了终点标记为1, 搜索结束
			break;
		}
		// 往四个方向拓展
		for(int i = 0; i < 4; i++) {
			int x = p.first + dx[i];
			int y = p.second + dy[i];
			if (x >= 0 && x < N && y >= 0 && y < M && map[x][y] != '#' && !visit[x][y]) {
				visit[x][y] = 1;    // 未出界且未访问过的格子，设置成已访问
				que.push(P(x,y));    // 入队
				step[x][y] = step[p.first][p.second] + 1;    // 步数 + 1
			}
		}
		que.pop(); // 队首元素出队，即p出队，之后搜索的是p的四周相邻且入队了的格子
	}

	if (flag == 0) {
		return -1; // 没有找到终点
	} else {
		return step[ex][ey]; // 找到了终点
	}
}