您的位置:澳门402永利com > 关于计算机 > 拯救炜哥

拯救炜哥

发布时间:2019-11-12 08:20编辑:关于计算机浏览(179)

    2843 拯救炜哥,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 }
    

     

    拯救炜哥,2843拯救炜 2843 拯救炜哥 时间限制: 2 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 有一天,炜哥和欧能干一起...

    本文由澳门402永利com发布于关于计算机,转载请注明出处:拯救炜哥

    关键词:

上一篇:浅议Delphi中的Windows API调用

下一篇:没有了