「RQNOJ34」紧急援救
题目描述
话说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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include <iostream> #include <cstring> #include <cstdio> using namespace std; int n; int a[1001][1001]; int xp[4]={0,0,-1,1}, yp[4]={1,-1,0,0}; int xx,yy; struct data{ int x,y,step; }dl[1000000]; int pr(int x,int y) { if(x==xx&&y==yy)return 1; else return 0; } int pd(int x,int y) { if(x>=1&&y>=1&&x<=n&&y<=n&&a[x][y]==0) return true; else return false; } void bfs() { int x,y,t=1,w=1; cin>>x>>y>>xx>>yy; a[x][y]=1; dl[t].x=x;dl[t].y=y;dl[t].step=0; if(pr(x,y)) {cout<<dl[t].step<<endl;return;} while(t<=w) { for(int i=0;i<4;i++) {x=dl[t].x+xp[i];y=dl[t].y+yp[i]; if(pd(x,y)) { a[x][y]=1; w++; dl[w].x=x;dl[w].y=y;dl[w].step=dl[t].step+1; if(pr(x,y)){cout<<dl[w].step<<endl; return;} } } t++; } } int main() { cin>>n; char s[1001]; for(int i=1;i<=n;i++) { scanf("%s",s); for(int j=0;j<n;j++) a[i][j+1]=s[j]-'0'; } bfs(); //system("pause"); return 0; } |
Subscribe
计数器 9713901
OI 课件=>
OI 课件=>