一个迷宫,其中的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)
蒟蒻能走通一些迷宫(如样例),但对于某个蒟蒻自创迷宫:
0 0 0 0 0
1 1 1 1 0
0 0 0 0 0
0 0 1 1 1
0 0 0 0 0
蒟蒻表示不会走(QAQ)
#include <bits/stdc++.h>
using namespace std;
int Map[10][10];
bool bj[10][10];
int be_x=0,be_y=0,en_x=4,en_y=4;
int wz[100][2];
int pre[100];
int fx[4]={1,-1,0,0},fy[4]={0,0,-1,1};
int head,tail;
bool pd;
int print(int t)
{
if(t>1)
{
print(pre[t]);
}
cout<<'('<<wz[t][0]<<", "<<wz[t][1]<<')'<<endl;
}
void bfs()
{
tail=1;
head=0;
wz[tail][0]=be_x;
wz[tail][1]=be_y;
pre[tail]=head;
bj[be_x][be_y]=1;
while(head!=tail)
{
head++;
for(int i=0;i<4;i++)
{
int x=fx[i]+wz[head][0];
int y=fy[i]+wz[head][1];
if(bj[x][y]==0 && Map[x][y]==0)
{
tail++;
bj[x][y]=1;
pre[tail]=head;
wz[tail][0]=x;
wz[tail][1]=y;
if(x==en_x && y==en_y)
{
print(tail);
pd=1;
break;
}
}
}
if(pd) break;
}
}
int main()
{
for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++)
{
cin>>Map[i][j];
}
}
bfs();
return 0;
}