177. 噩梦（ bfs）

妖狐艹你老母 2021-11-10 23:14 264阅读 0赞

题目链接：[https://www.acwing.com/problem/content/179/][https_www.acwing.com_problem_content_179]  
给定一张N\*M的地图，地图中有1个男孩，1个女孩和2个鬼。

字符“.”表示道路，字符“X”表示墙，字符“M”表示男孩的位置，字符“G”表示女孩的位置，字符“Z”表示鬼的位置。

男孩每秒可以在道路上移动3个单位距离，女孩每秒可以在道路上移动1个单位距离。

每个鬼占据的区域每秒可以向四周扩张2个单位距离，并且无视墙的阻挡，也就是在第k秒后所有与鬼的曼哈顿距离不超过2k的位置都会被鬼占领。

求在不进入鬼的占领区的前提下，男孩和女孩能否会合，若能会合，求出最短会合时间。  
输入格式

第一行包含整数T，表示共有T组测试用例。

每组测试用例第一行包含两个整数N和M，表示地图的尺寸。

接下来N行每行M个字符，用来描绘整张地图的状况。（注意：地图中一定有且仅有1个男孩，1个女孩和2个鬼）  
输出格式

每个测试用例输出一个整数S，表示最短会合时间。

如果无法会合则输出-1。

每个结果占一行。  
数据范围

1<n,m<800

输入样例：

3  
5 6  
XXXXXX  
XZ…ZX  
XXXXXX  
M.G…  
…  
5 6  
XXXXXX  
XZZ…X  
XXXXXX  
M…  
…G…  
10 10  
…  
…X…  
…M.X…X.  
X…  
.X…X.X.X.  
…X  
…XX…X.  
X…G…X  
…ZX.X…  
…Z…X…X

输出样例：

1  
1  
\-1

分析：今夜是想哭的一天。  
感觉回到了大一的bug时代。我也不知道为什么，但是它就是错了。我也很绝望。明明就是一样的，重敲一遍，怎么就过了呢。5555~~~  
这个题，我们可以在bfs的时候，同时bfs男孩，女孩，和鬼。如果男孩和女孩能够同时相遇，那么就返回值。注意，男孩要bfs三次，女孩1次，鬼两次。  
思路很简单。  
我的wa点  
1，char打成了int。自己这个智障玩意  
2，bfs三次，直接把队头的值记录下来就好了，非要傻逼搞。  
3，我爆队列了，明显标记打错了。可是我找不到 555

#include"stdio.h"
    #include"string.h"
    #include"math.h"
    #include"queue"
    #include"algorithm"
    using namespace std;
    #define INF 1001010
    typedef struct Node
    {
        int x,y,t;
        Node(int a,int b,int c)
        {
            x = a; y = b; t = c;
        }
        Node()
        {
    
        }
    }Node;
    
    const int dir[4][2] = {
       {-1,0},{1,0},{0,1},{0,-1}};
    
    int T,N,M;
    char Graph[810][810];
    int min_k;
    
    int check(int x,int y)
    {
       if(x >= 1 && x <= N && y >= 1 && y <= M)    return 1;
       return 0;
    }
    
    int bfs()
    {
        queue<Node> man,girl,ghost;
    
    
        for(int i = 1; i <= N; i ++)
            {
                for(int j = 1; j <= M; j ++)
                {
                    if(Graph[i][j] == 'G')
                        {
                           // printf("%c i = %d j = %d\n",Graph[i][j],i,j);
                            girl.push({i,j,0});
                        }
                    if(Graph[i][j] == 'M')
                        {
                           //printf("%c i = %d j = %d\n",Graph[i][j],i,j);
    
                            man.push({i,j,0});
                            //vis_man[i][j] = 1;
                        }
                    if(Graph[i][j] == 'Z')
                    {
                        ghost.push({i,j,0});
                        //vis_woman[i][j] = 1;
                    }
                }
            }
        for(int i = 1; i <= 100000; i ++)
        {
           int flag = ghost.front().t;
           while(!ghost.empty() && ghost.front().t < flag + 2)
           {
               Node T = ghost.front(); ghost.pop();
               int x = T.x;
               int y = T.y;
               for(int j = 0; j < 4;j ++)
               {
                   int x1 = x + dir[j][0];
                   int y1 = y + dir[j][1];
                   if(check(x1,y1) && Graph[x1][y1] != '#')
                   {
                       Graph[x1][y1] = '#';Graph[x][y] = '#';
                       ghost.push({x1,y1,T.t + 1});
                   }
               }
           }
           flag = man.front().t;
           while(!man.empty() && man.front().t < flag + 3)
           {
               Node T = man.front(); man.pop();
               int x = T.x;
               int y = T.y;
               for(int j = 0; j < 4; j ++)
               {
                   int x1 = x + dir[j][0];
                   int y1 = y + dir[j][1];
                   if(Graph[x1][y1] == 'G') return i;
                   if(check(x1,y1) && Graph[x1][y1] == '.')
                   {
                       Graph[x1][y1] = 'M'; Graph[x][y] = 'X';
                       man.push({x1,y1,T.t + 1});
                   }
               }
           }
           flag = girl.front().t;
           while(!girl.empty() && girl.front().t < flag + 1)
           {
               Node T = girl.front(); girl.pop();
               int x = T.x;
               int y = T.y;
               for(int j = 0; j < 4; j ++)
               {
                   int x1 = x + dir[j][0];
                   int y1 = y + dir[j][1];
                   if(Graph[x1][y1] == 'M') return i;
                   if(check(x1,y1) && Graph[x1][y1] == '.')
                   {
                       Graph[x1][y1] = 'G';Graph[x][y] = 'X';
                       girl.push({x1,y1,T.t + 1});
                   }
               }
           }
        }
        return -1;
    }
    
    int main()
    {
        scanf("%d",&T);
        while(T --)
        {
            scanf("%d%d",&N,&M);
            int cnt = 0;
            for(int i = 1; i <= N; i ++)
                {
                   scanf("%s",Graph[i] + 1);
                }
            int T = bfs();
            printf("%d\n",T);
        }
    }

[https_www.acwing.com_problem_content_179]: https://www.acwing.com/problem/content/179/