讨论 / 这分明就是bfs
xyz32768 2016-12-22 22:49:00
点我顶贴 收藏 删除
#include <iostream>

using namespace std;

int m,n,sx,sy,ex,ey,head,tail,qx[4500001],qy[4500001],st[4500001],

xp[4]={1,-1,0,0},yp[4]={0,0,-1,1};

bool b[2001][2001];

int main()

{

int i,j,x;

cin>>m>>n;

for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

{

cin>>x;

b[i][j]=(x==1)?1:0;

}

cin>>sx>>sy>>ex>>ey;

head=0;tail=1;qx[1]=sx;qy[1]=sy;st[1]=0;b[sx][sy]=1;

if(sx==ex && sy==ey) {cout<<st[1];return 0;}

do

{

head++;

for(i=0;i<4;i++)

if(qx[head]+xp[i]>=1 && qx[head]+xp[i]<=m

&& qy[head]+yp[i]>=1 && qy[head]+yp[i]<=n

&& !b[qx[head]+xp[i]][qy[head]+yp[i]])

{

tail++;

qx[tail]=qx[head]+xp[i];

qy[tail]=qy[head]+yp[i];

st[tail]=st[head]+1;

b[qx[tail]][qy[tail]]=1;

if(qx[tail]==ex && qy[tail]==ey)

{cout<<st[tail];return 0;}

}

} while(head<tail);

cout<<"No Answer!";

return 0;

}

查看更多回复
提交回复