2177: 信息学奥赛一本通T1252-走迷宫（bfs模板）

解题思路:
可以把bfs当成扩散问题，如果下一步可以走，就向下一步扩散，直到遇见终点，停止循环。

参考代码:

#include <bits/stdc++.h>
#include <queue>
using namespace std;

const int S=41;//题目范围最大为40

struct node{
	int x,y,l;//横坐标和纵坐标  l为当前为第几步
};

int dx[4]={1,-1,0,0};//上 下 左 右 
int dy[4]={0,0,-1,1};
bool vis[S][S];//记录走没有走过
char p[S][S];
queue<node>q;//队列

void bfs(int n,int m){
	q.push({1,1,1}); //起点从（1,1）开始 当前为第一步
	
	while(!q.empty()){//队列不为空
		node now=q.front();
		vis[now.x][now.y]=1;//走过 标记为1
		q.pop();//取出队首 （队首已经在新创建的now中）
		
		if(now.x==n&&now.y==m){//找到终点，打印，结束循环
			cout<<now.l<<endl;
			break;
		}
		for(int i=0;i<4;i++){//上下左右的寻找
			int x=now.x+dx[i];
			int y=now.y+dy[i];
			if(x>0&&y>0&&x<=n&&y<=m){
				if(p[x][y]=='.'&&vis[x][y]==0){//可以走而且没有走过，放入队列
					vis[x][y]=1;//已经走过了，标记为1
					q.push({x,y,now.l+1});
				}
			}	
		}
	}
}

int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>p[i][j];
		}
	}
	bfs(n,m);

 	return 0;
}