【题目描述】

一个迷宫由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;  }

(adsbygoogle = window.adsbygoogle || []).push({});