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

5

数据范围及提示

Data Size & Hint

1<=n,m<=1000

最后一个测试数据有误

1 #include
          
            2 #include
           
             3 #include
            
              4 #include
             
               5 using namespace std; 6 struct node{ 7     int x,y,s; 8 }cur,net; 9 queue
              
               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<