牛客 走出迷宫＜每日一题分享＞（bfs基础题目）

牛客 走出迷宫＜每日一题分享＞（bfs基础题目）

题目链接：登录—专业IT笔试面试备考平台_牛客网

题目

 代码详解：

#include
using namespace std;
#include
#include
int m, n, endx, endy;
char map[503][503];//存储迷宫
struct fx
{
	int x;
	int y;
}around[] = { {0,1},{-1,0},{1,0},{0,-1} };
//方向结构体的设计，让小明能往四处走
int main()
{
	while (cin >> n >> m)//当不存在输入的时候停止
	{
		bool flag = 0;//falg作为标记是否能到达终点
		fx now;//定义结构体now标记位置
		memset(map, 0, sizeof map);//每次重新输入地图需要对地图清零并重新填写
		bool vis[503][503] = { 0 };//标记该处是否被走过
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= m; j++)
			{
				char s;
				cin >> s;
				map[i][j] = s;
				if (map[i][j] == 'S')//找到起点的位置
				{
					now.x = i;
					now.y = j;
					vis[i][j] = 1;
				}
			}
		}
		queue p;
		p.push(now);//将一开始的位置放入p中
		while (!p.empty())//当p中没有能继续走的情况退出循环
		{
			now = p.front();
			p.pop();//进行该位置的四处走动，并在p中消除该位置
			for (int i = 0; i < 4; i++)//四处走动
			{
				int nx = now.x + around[i].x;
				int ny = now.y + around[i].y;
				if (map[nx][ny] == 'E')
				{
					flag = 1;
					break;
				}//找到终点,直接输出
				if (vis[nx][ny]) continue;//如果被走过直接继续循环
				if (nx <= n && ny <= m && nx >= 1 && ny >= 1 && map[nx][ny] != '#')//走动到的该位置没有障碍且在地图内
				{
					p.push({ nx,ny });//将能到达的该点放入p中
					vis[nx][ny] = 1;//标记该位置已经被探索
				}
			}
		}
		if (flag)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
	return 0;
}

总结：bfs对于细节把握要求能力较强，一个小错误会让你不得不debug很久，所以每一步都需要仔细的斟酌，记住bfs的一般套路

PS:学如逆水行舟，不进则退，坚持会为你的胜利的护航！加油！