信息学奥赛一本通 1255：迷宫问题 广度优先搜索算法
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。时间限制: 1000 ms内存限制: 65536 KB。一个5 × 5的二维数组，表示一个迷宫。左上角到右下角的最短路径，格式如样例所示。
·
1255：迷宫问题
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
定义一个二维数组：
int maze[5][5] = {
0,1,0,0,0,
0,1,0,1,0,
0,0,0,0,0,
0,1,1,1,0,
0,0,0,1,0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
【输入】
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
【输出】
左上角到右下角的最短路径，格式如样例所示。
【输入样例】
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
【输出样例】
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
#include<bits/stdc++.h>
using namespace std;
int n=5;
bool a[10][10];//表示地图
bool b[10][10];//表示走没走过
queue <int>qx;
queue <int>qy;
int vx[10][10];
int vy[10][10];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void bfs(int x,int y){
qx.push(x);
qy.push(y);
b[x][y]=1;
while (!qx.empty()){
x=qx.front();
y=qy.front();
qx.pop();
qy.pop();
for(int i=0;i<4;i++){
int xx=dx[i]+x;
int yy=dy[i]+y;
if (xx>0&&xx<=n&&yy>0&&yy<=n&&b[xx][yy]==0&&a[xx][yy]==0){
vx[xx][yy]=x;
vy[xx][yy]=y;
b[xx][yy]=1;
qx.push(xx);
qy.push(yy);
if (xx==n&&yy==n){
return;
}
}
}
}
}
void myprint(int x,int y){
if (x==0&&y==0) return;
int xx=vx[x][y];
int yy=vy[x][y];
myprint(xx,yy);
cout<<"("<<x-1<<", "<<y-1<<")"<<endl;
}
int main() {
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
bfs(1,1);
myprint(n,n);
return 0;
}
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
6
0- 0
已为社区贡献6条内容
所有评论(0)