【题目描述】

一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。

给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。

【输入描述】

第一行是两个整数，Ｒ和Ｃ，代表迷宫的长和宽。（ 1<= R，C <= 40)

接下来是Ｒ行，每行Ｃ个字符，代表整个迷宫。

空地格子用‘.’表示，有障碍物的格子用‘#’表示。

迷宫左上角和右下角都是‘.’。

【输出描述】

【样例输入】

5 5
..###
#....
#.#.#
#.#.#
#.#..

【样例输出】

9

【题目分析】

/*
bfs 走迷宫
*/
#include<bits/stdc++.h>
using namespace std;
int r,c;
char maps[105][105];
bool vis[105][105];
int dir[4][2]= {{-1,0},
	{1,0},
	{0,-1},
	{0,1}
};
struct node {
	int x;
	int y;
	int step;
} q[100100];

void bfs(int sx,int sy,int ex,int ey) {
	int head=1,tail=1;  //定义头指针和尾指针 
	memset(vis,0,sizeof(vis));
	vis[sx][sy]=1;
	q[tail].x=sx;
	q[tail].y=sy; 
	q[tail].step=1;
	tail++;

	while(head<tail) {
		int x=q[head].x;
		int y=q[head].y;
		int step=q[head].step;
		if(x==ex&&y==ey) {  //遇到目标点就输出 
			cout<<step<<endl;
			break;
		}
		for(int i=0; i<4; i++) {
			int nx=x+dir[i][0];
			int ny=y+dir[i][1];
			if(nx>=0&&nx<r&&ny>=0&&ny<c&&vis[nx][ny]==0&&maps[nx][ny]=='.') {
				vis[nx][ny]=1;
				q[tail].x=nx;
				q[tail].y=ny;
				q[tail].step=step+1;
				tail++;
			}
		}
		head++;
	}
}
int main() {
	cin>>r>>c;
	for(int i=0; i<r; i++)
		cin>>maps[i];
	bfs(0,0,r-1,c-1);
	return 0;
}