1755 - 营救
【问题描述】 铁达尼克号遇险了
它发出了求救信号。距离最近的哥伦比亚号收到了讯息。时间就是生命，必须尽快赶到那里通过侦测，哥伦比亚要获取了一张海洋图
这张海洋图上划分成了nn个比较小的单位，用1表示陆地 用0表示海洋 船只能从一个格子移到相邻的4个格子里。
为了尽快赶到出事地点，哥伦比亚号最少要走多少距离。
【输入格式】 save.in
第一行，n 以下的nn行为一个0，1矩阵，表示海洋地图
最后一行为4个小于n的整数 表示 哥伦比亚号 和铁达尼克号的坐标
【输出格式】save.out
哥伦比亚号到铁达尼克号的最短距离 ，答案精确到整数。
<b><span>Input</span> </b>
<span> 【样例输入】3 <br />
001
101
100
1 1 3 3
<b><span>Output</span> </b>
<span> 4</span>
<span> N<=1000 </span>
Input
Output
Examples
Input
Output
Solution C++
#include<iostream> using namespace std; int n,x1,x2,y1,y2,h=0,r=1;; char a[1001][1001]; int b[1000000][4],c[1001][1001]={0}; int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; void bfs(); int main() { cin>>n; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) cin>>a[i][j]; cin>>x1>>y1>>x2>>y2; bfs(); return 0; } void bfs() { int x,y; b[1][1]=x1; b[1][2]=y1; b[1][3]=0; c[x1][y1]=1; while(h<r) { ++h; for(int i=0;i<4;++i) { x=b[h][1]+dx[i]; y=b[h][2]+dy[i]; if(x>0&&x<=n&&y>0&&y<=n&&!c[x][y]&&a[x][y]=='0') { c[x][y]=1; ++r; b[r][1]=x; b[r][2]=y; b[r][3]=b[h][3]+1; } if(x==x2&&y==y2) { cout<<b[r][3]; return; } } } }