2858 - 失踪的博士
失踪的博士
话说2007年8月5日，Mike博士神秘失踪了，最后发现是被外星人绑架了，幸好外星人目前还是在地球上活动，并且知道外星人不了解地球，幸好，Milk博士身上有无线信号发送装置，我们终于确定了他的位置，必须赶快到那里去救他。
根据无线信号发送装置，我们确定出一张地图，为了尽快寻找到Mike博士，于是这个光荣和艰巨的任务便交给了你，编写程序，通过使用一张地图帮助研究所确定从研究所出发找到Mike博士最短距离。
题目输入
数据范围： n<=1000
输入格式
第一行为n
第二行为n*n的地图（其中0表示通路，1表示死路）
最后两行每行有两个数字，分别表示研究所的坐标和博士信号所在的位置。
题目输出
一个数字k，表示从研究所出发找到Milk博士的最短距离。
输入/输出样例
题目输入
10 0100110100 0001110010 1000000001 1000100011 0000101100 1000001100 1001010011 0000010100 0101010000 1001000001 1 7 10 2
题目输出
14
提示
作者：刘子昂
C++解答
#include<stdio.h> #include<queue> using namespace std; struct node { int x,y; }; int main() { int n; while(scanf("%d",&n)!=EOF) { char a[1000][1000]; int bb[1000][1000]; getchar(); queue<node>q; for (int i=0;i<n;i++) { scanf("%s",a[i]); getchar(); } node as,ab; scanf("%d%d",&as.x,&as.y); as.x--;as.y--; scanf("%d%d",&ab.x,&ab.y); ab.x--;ab.y--; a[as.x][as.y]='1'; q.push(as);int all=0; bb[as.x][as.y]=0; while(!q.empty()) { if (q.front().x==ab.x&&q.front().y==ab.y) {break;} else { node ww; all=bb[q.front().x][q.front().y]; if (q.front().x-1>=0&&a[q.front().x-1][q.front().y]=='0') {bb[q.front().x-1][q.front().y]=all+1;a[q.front().x-1][q.front().y]='1';ww.x=q.front().x-1;ww.y=q.front().y;q.push(ww);} if (q.front().y-1>=0&&a[q.front().x][q.front().y-1]=='0') {bb[q.front().x][q.front().y-1]=all+1;a[q.front().x][q.front().y-1]='1';ww.x=q.front().x;ww.y=q.front().y-1;q.push(ww);} if (q.front().y+1<=n-1&&a[q.front().x][q.front().y+1]=='0') {bb[q.front().x][q.front().y+1]=all+1;a[q.front().x][q.front().y+1]='1';ww.x=q.front().x;ww.y=q.front().y+1;q.push(ww);} if (q.front().x+1<=n-1&&a[q.front().x+1][q.front().y]=='0') {bb[q.front().x+1][q.front().y]=all+1;a[q.front().x+1][q.front().y]='1';ww.x=q.front().x+1;ww.y=q.front().y;q.push(ww);} } q.pop(); } printf("%d\n",bb[ab.x][ab.y]); } return 0; }
提示
作者：刘子昂