2843 拯救炜哥

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

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

分类标签 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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BZOJ3295: [Cqoi2011]动态逆序对(cdq分治)

    对于序列A,它的逆序对数定义为满足i<j,且Ai>Aj的数对(i,j)的个数。给1到n的一个排列,按照某种顺序依次删

    attack
  • 1576 最长严格上升子序列

    1576 最长严格上升子序列 时间限制: 1 s 空间限制: 256000 KB 题目等级 : 黄金 Gold 题目描述 Description ...

    attack
  • P1903 【模板】分块/带修改莫队(数颜色)

    题目描述 墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令: 1、 Q L R代表询问你从第L支画笔到...

    attack
  • 【POJ1456】Supermarket(贪心)

    每个商品有过期日期和价格,每天可以卖一个商品,必须在过期前出售才能收益,求最大收益。

    饶文津
  • LeetCode第166场周赛题解

    这是LeetCode的第166场周赛的题解,不出意外的又爆炸了,前三题只做了20分钟,第4题因为题意读错了耽误了40分钟,到1小时15分钟左右才写完。排名直接1...

    BBuf
  • Idea 使用 Junit4 进行单元测试

    Idea 默认使用 arquillian junit4 作为测试框架,我们将其更改为 Junit4。

    希希里之海
  • 【USACO 1.2】Palindromic Squares

    饶文津
  • 1035. 插入与归并(25)

    插入排序是迭代算法,逐一获得输入数据,逐步产生有序的输出序列。每步迭代中,算法从输入序列中取出一元素,将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

    AI那点小事
  • 1065. 单身狗(25)

    “单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人,以便给予特殊关爱。

    AI那点小事
  • C++初始化

    Qt君

扫码关注云+社区

领取腾讯云代金券