2177走迷宫 简单BFS(注释很详细)

在求解最短路问题时,深度优先搜索会反复经过相同的状态,广度优先搜索只会遍历每个点一遍,

所以对于该类问题,深度优先搜索性能不如广度优先搜索好,广度优先搜索适合求解该类问题.

显然这道题用BFS更好.

/*BFS思想:从同一起点出发,每次都向前走一步,更短的路径一定会更快地到达终点,
终点的层数(到达要花的步数)也会相应地更新为最小层数*/

#include<bits/stdc++.h>

using namespace std;

#define INF 9999999;

int R,C;

int i,j;

typedef struct Point
{
	int x;
	int y;
	char cell;//单元格cell('.'或者'#')
	int layer;//方便BFS的层数(layer)统计,同时也可以表示到达一点要花的步数
}Point;

Point M[1005][41];//Point Map

int book[1005][41];//用于判断该点是否走过

int nx,ny;//next_x,next_y

int sx = 1, sy = 1;//start_x,start_y起点坐标

int ex,ey;//end_x,end_y终点坐标

Point point;

queue <Point> que;

int Next[4][2] = {{0,-1},{-1,0},{0,1},{1,0}};
//方向数组,next[i][0]表示行坐标,next[i][1]表示列坐标
//左上右下的顺序

int main()
{
	scanf("%d %d",&R,&C);
	getchar();
	
	for(i = 1; i <= R;i++)
	{
		for(j = 1; j <= C; j++)
		{
			scanf("%c",&M[i][j].cell);
			M[i][j].x = i;
			M[i][j].y = j;
			M[i][j].layer = INF;
			//初始化为INF,即到达不了
		}
		getchar();//一定要加,不然就会地图读取错误
	}
	
	que.push(M[sx][sy]);
	book[sx][sy] = 1;
	M[sx][sy].layer = 1;
	//从地图左上角出发
	//如果有从其他地方出发的需求可以改值
	
	ex = R;
	ey = C;
	//设置终点
	
	while(que.empty() != 1)
	{
		point = que.front();
		que.pop();
		//接收到队首元素后就弹出队首元素(不需要它了)
		
		for(i = 0; i <= 3; i++)
		{
			nx = point.x + Next[i][0];
			ny = point.y + Next[i][1];
			
			if(nx>= 1 && nx <= R && ny >=1 && ny <= C//不出界
			&& M[nx][ny].cell == '.' && book[nx][ny] == 0)//是空地格子并且没有走过
			{
				book[nx][ny] = 1;//标记为走过
				
				M[nx][ny].layer = M[point.x][point.y].layer + 1;//意为:多一步就可以到
				
				que.push(M[nx][ny]);//入队
				
				if(nx == ex && ny == ey)
				{
					break;
					//剪枝
					//如果终点已经入队了,证明终点的步数就已经确定了,不用再进行了
				}
			}
		}
		if(nx == ex && ny == ey)
		{
			break;
			//继续跳出循环
		}
	}
	
	cout << M[ex][ey].layer;
	
	return 0;
}