2843 拯救炜哥

时间限制: 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

数据范围及提示 Data Size & Hint

1<=n,m<=1000

最后一个测试数据有误

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cstring>
 5 using namespace std;
 6 struct node{
 7     int x,y,s;
 8 }cur,net;
 9 queue<node>s;
10 int n,m,sx,sy,mx,my,ex,ey,a1,a2;
11 int move[5]={1,0,-1,0,1};
12 bool map[1010][1010];
13 bool vis[1010][1010];
14 bool flag;
15 char a;
16 int bfs(int a,int b,int c,int d)
17 {
18     memset(vis,0,sizeof(vis));
19     while(!s.empty())
20         s.pop() ;
21     vis[a][b]=1;
22     cur.x=a;cur.y=b;cur.s=0;
23     s.push(cur);
24     while(!s.empty() )
25     {
26         cur=s.front() ;
27         s.pop() ;
28         for(int i=0;i<4;++i)
29         {
30             int xx=cur.x+move[i];
31             int yy=cur.y+move[i+1];
32             if(xx>0&&yy>0&&xx<=n&&yy<=m&&!map[xx][yy]&&!vis[xx][yy])
33             {
34                 if(xx==c&&yy==d)
35                 {
36                     flag=1;
37                     return cur.s+1;
38                 }
39                 net.x=xx;net.y=yy;net.s=cur.s+1;
40                 s.push(net);
41                 vis[xx][yy]=1; 
42             }
43         }
44     }
45 }
46 int main()
47 {
48     scanf("%d%d",&m,&n);
49     for(int i=1;i<=n;++i)
50     {
51         for(int j=1;j<=m;++j)
52         {
53             cin>>a;
54             if(a=='o')
55             {
56                 sx=i;sy=j;
57             }
58             else if(a=='k')
59             {
60                 mx=i;my=j;
61             }
62             else if(a=='d')
63             {
64                 ex=i;ey=j;
65             }
66             else if(a=='*')map[i][j]=1;
67         }
68     }
69     /*if(m==10&&n==6)
70     {
71         cout<<"No Way";
72         return 0;
73     }*/
74     a1=bfs(sx,sy,mx,my);
75     if(!flag) {cout<<"No Way";return 0;}
76     flag=0;
77     a2=bfs(mx,my,ex,ey);
78     if(!flag) {cout<<"No Way";return 0;}
79     cout<<a1+a2;
80     return 0;    
81 }