A45682. 迷宫问题定义一个二维数组：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 的二维数组， 表示一个迷宫。…
填空题
困难
知识点
题目描述
迷宫问题
定义一个二维数组：
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<cstdio>
#include<iostream>
#include<queue>
using namespace std;
typedef long long ll;
int m[4][2]={1,0,0,1,-1,0,0,-1};
int s[10][10],vis[10][10];
struct node{
int x,y;
}step[10][10];
void print(node p){
if(p.x==0 && p.y==0){
printf("(0, 0)\n");
return;
}
print(step[p.x][p.y]);
printf("(%d, %d)\n",p.x,p.y);
}
void bfs(){
fill(vis[0],vis[0]+10*10,0);
node a,b;
queue<node>q;
a.x=0,a.y=0;
vis[0][0]=1;
q.push(a);
while(!q.empty()){
a=q.front();
q.pop();
if(a.x==4 && a.y==4){
print(a);
break;
}
for(int i=0;i<4;i++){
b.x=a.x+m[i][0],b.y=a.y+m[i][1];
if(s[b.x][b.y]==0 && b.x>=0 && b.y<5 && b.x>=0 && b.y<5 && !vis[b.x][b.y]){
vis[b.x][b.y]=1;
step[b.x][b.y]=a;
q.push(b);
}
}
}
}
int main(){
for(int i=0;i<5;i++){
for(int j=0;j<5;j++)
cin>>s[i][j];
}
bfs();
return 0;
}
上一题
下一题