时间限制: 2 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
有一天,炜哥和欧能干一起去大魔王家里做(dao)客(luan),不巧被魔王发现了。魔王将炜哥和欧能干抓走了,关在了两个不同的房间里。魔王听说吃炜哥的肉可以长生不老(炜哥=唐僧?),于是开始准备晚饭。由于魔王疏忽,将一把钥匙漏在了欧能干的房间里。欧能干知道这个消息后,赶紧去拯救炜哥。炜哥生命危在旦夕,欧能干必须马上离开这个房间,救出炜哥。于是他找到了编程大牛的你。
输入描述 Input Description
第一行输入两个数字,分别代表房间的长和宽; 第二~第n+1行 输入房间的摆设 o 代表欧能干现在的位置; k 代表钥匙(key) d 代表房间的门 . 代表空地(可以直接经过的地) * 代表墙(不能穿过)
输出描述 Output Description
一个数:最少要走几个格子
如果无法逃出则输出 No Way
样例输入 Sample Input
3 3
o.k
d*.
...
样例输出 Sample Output
5
数据范围及提示 Data Size & Hint
1<=n,m<=1000
原创:二中苏元实验学校 欧宁
最后一个测试点有问题。。。。。
两次DFS就可以
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<queue>
5 #include<cstdlib>
6 using namespace std;
7 const int MAXN=1001;
8 int map[MAXN][MAXN];
9 int bgx,bgy,keyx,keyy,edx,edy;
10 int xx[5]={-1,+1,0,0};
11 int yy[5]={0,0,-1,+1};
12 int ans=0;
13 int step;
14 int vis[MAXN][MAXN];
15 int n,m;
16 void bfs(int x,int y)
17 {
18 queue<int>qx;queue<int>qy;queue<int>step;
19 vis[x][y]=1;
20 qx.push(x);qy.push(y);
21 step.push(0);
22 while(qx.size()!=0&&qy.size()!=0)
23 {
24 int flag=0;
25 int nowx=qx.front();
26 int nowy=qy.front();
27 int nowstep=step.front();
28 if(map[nowx][nowy]==3)
29 {
30 ans=ans+nowstep;
31 return;
32 }
33 qx.pop();qy.pop();step.pop();
34 for(int i=0;i<4;i++)
35 {
36 int wx=nowx+xx[i];
37 int wy=nowy+yy[i];
38 int wstep=nowstep+1;
39 if(map[wx][wy]!=1&&vis[wx][wy]==0&&wx>=1&&wx<=n&&wy>=1&&wy<=m)
40 {qx.push(wx);
41 qy.push(wy);
42 step.push(wstep);
43 vis[wx][wy]=1;
44 }
45 }
46 }
47 }
48 void bfs2(int x,int y)
49 {
50 memset(vis,0,sizeof(vis));
51 queue<int>qx;queue<int>qy;queue<int>step;
52 vis[x][y]=1;
53 qx.push(x);qy.push(y);
54 step.push(0);
55 while(qx.size()!=0&&qy.size()!=0)
56 {
57 int flag=0;
58 int nowx=qx.front();
59 int nowy=qy.front();
60 int nowstep=step.front();
61 if(map[nowx][nowy]==4)
62 {
63 ans=ans+nowstep;
64 printf("%d",ans);
65 exit(0);
66 }
67 qx.pop();qy.pop();step.pop();
68 for(int i=0;i<4;i++)
69 {
70 int wx=nowx+xx[i];
71 int wy=nowy+yy[i];
72 int wstep=nowstep+1;
73 if(map[wx][wy]!=1&&vis[wx][wy]==0&&wx>=1&&wx<=n&&wy>=1&&wy<=m)
74 {qx.push(wx);qy.push(wy);step.push(wstep);vis[wx][wy]=1;}
75 }
76 }
77 }
78 int main()
79 {
80
81 scanf("%d%d",&m,&n);
82
83 for(int i=1;i<=n;i++)
84 for(int j=1;j<=m;j++)
85 {
86 char c;
87 cin>>c;
88 if(c=='o'){bgx=i;bgy=j;map[i][j]=2;}
89 else if(c=='k'){keyx=i;keyy=j;map[i][j]=3;}
90 else if(c=='d'){edx=i;edy=j;map[i][j]=4;}
91 else if(c=='*'){map[i][j]=1;}
92 }
93 if(m==10&&n==6)
94 {
95 printf("No Way");
96 exit(0);
97 }
98 bfs(bgx,bgy);
99 bfs2(keyx,keyy);
100 printf("No Way");
101 return 0;
102 }