用广度优先搜索做了一个迷宫,照着样例输入数据输入了一个迷宫,但是输出却是无解,为啥?
输入数据:
#####
S...#
###.#
#...#
#..##
#...#
###.#
#E..#
井号是障碍,点是空位
入口是S,出口是E
代码:
#include<bits/stdc++.h>
using namespace std;
#define False false
#define True true
#define None 0
int u[5]={0, 0, 1, 0, -1};
int w[5]={0, 1, 0, -1, 0};
int n, m, desx, desy, soux, souy, head, tail, x, y, a[101], b[101], pre[101], _map[101][101];
bool f;
void out(int d)
{
if(pre[d]!=0)
{
out(pre[d]);
}
printf("%d, $d\n", a[d], b[d]);
}
int main()
{
cin>>n>>m; // The maze with n rows and m columns.
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>_map[i][j];
}
}
cout<<"Input the enter: ";
scanf("%d%d", &soux, &souy);
cout<<"Input the exit: ";
scanf("%d%d", &desx, &desy);
head=0;tail=1;f=False;
_map[soux][souy]=-1;
while(head!=tail) // Judge that queue isn't empty.
{
head++;
for(int i=1;i<=4;i++)
{
x=a[head]+u[i];y=b[head]+w[i];
if((x>0)&&(x<n)&&(y>0)&&(y<m)&&_map[x][y]==0)
{ // If this direction is avaliable then?
tail++;
a[tail]=x;b[tail]=y;pre[tail]=head;
_map[x][y]=-1; // """Break the bridge after you crossed the river""" //
if((x==desx)&&(y==desy))
{
f=True;
out(tail);
break;
}
}
}
if(f==1)
{
break;
}
}
if(f==0)
{
cout<<"NEVER"<<endl;
}
return 0;
}
我真的服了广度优先搜索,嘈