Problem1774--营救1774: 营救
Time Limit: 1.000 Sec Memory Limit: 128 MB
Submit: 649 Solved: 165
[Submit] [Status] [Web Board] [Creator:]Description
铁塔尼号遇险了！他发出了求救信号。距离最近的哥伦比亚号收到了讯息，时间就是生命，必须尽快赶到那里。
通过侦测，哥伦比亚号获取了一张海洋图。这张图将海洋部分分化成n*n个比较小的单位，其中用1标明的是陆地，用0标明是海洋。船只能从一个格子，移到相邻的四个格子。
为了尽快赶到出事地点，哥伦比亚号最少需要走多远的距离。
Input
第一行为n,下面是一个n*n的0、1矩阵，表示海洋地图(n<=1000)
最后一行为四个小于n的整数，分别表示哥伦比亚号和铁塔尼号的位置。
Output
哥伦比亚号到铁塔尼号的最短距离，答案精确到整数。
Sample Input
3
001
101
100
1 1 3 3
Sample Output
4
HINT
#include<bits/stdc++.h>
using namespace std;
int a[2000][2000];
int b[2000][2000];
int bs[2000][2000];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int x[1000001],y[10000001];
int h=0,t=0;
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
string s;
cin>>s;
for(int j=1;j<=n;j++)
a[i][j]=s[j-1]-'0';
}
int ax,ay,bx,by;
cin>>ax>>ay>>bx>>by;
if(ax==bx&&ay==by)
{
cout<<0;
return 0;
}
t++;
x[t]=ax;
y[t]=ay;
b[ax][ay]=1;
bs[ax][ay]=0;
while(h<=t)
{ h++;
int nx=x[h];
int ny=y[h];
for(int i=0;i<4;i++)
{
int xx=nx+dx[i];
int yy=ny+dy[i];
if(xx>=1&&yy>=1&&xx<=n&&yy<=n)
{
if(a[xx][yy]==0&&b[xx][yy]==0)
{ t++;
x[t]=xx;
y[t]=yy;
b[xx][yy]=1;
bs[xx][yy]=bs[nx][ny]+1;
if(xx==bx&&yy==by)
{
cout<<bs[xx][yy];
return 0;
}
}
}
}
}
}
Source/Category
[Submit] [Status]