游客 注册 | 登录
中文 | En

2858 - 失踪的博士

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

失踪的博士

话说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;
}
请先登陆