首页 > > 程序设计 > C/C++ >

2843 拯救炜哥

2018-06-17 22:42:50来源：未知阅读 ()

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

原创：二中苏元实验学校欧宁

分类标签 Tags 点此展开

最后一个测试点有问题。。。。。

两次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 }