xyz32768 2016-12-22 06: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;
}