【算法】走迷宫
【题目描述】
一个迷宫由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;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。