19. 大吉大利，晚上吃鸡

Dear 丶 2022-04-02 07:30 208阅读 0赞

Description

众所周知，现在吃鸡游戏非常流行，龙神也想在这个大流中捞一手，于是他也发明了一种吃鸡游戏。但是他非常讨厌伏地魔，想要有着完全制约伏地魔的手段，于是他决定给游戏里空投按钮，只要按下这个按钮，就可以直接吃鸡。但这样游戏不够混乱没有观赏性。所以龙神决定让所有玩家都不可以攻击，只能通过按下按钮来取胜，并且他决定空投许多个这样的按钮，只要按下其中之一就可以吃鸡。
        地图是一个矩阵，玩家每秒只能移动到相邻的格子中去。每个玩家都知道离自己最近的按钮在哪，并且他们都很想赢。
        龙神现在想知道每一局都在第几秒结束。

本来题目是这样的，可是龙神说这个题目太简单了，所以他还想知道游戏胜利的那个人走的路径。如果有多种路径输入其中任意一条就可以了。

Input

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTIwNzE3NQ_size_16_color_FFFFFF_t_70][]

#include <queue>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    const int maxn = 1005;
    const int dx[] = {1, -1, 0, 0};//右左下上
    const int dy[] = {0, 0, 1, -1};
    
    struct node {
        int x, y;
        int step;
        // 初始化列表
        node(int _x, int _y, int _step) : x(_x), y(_y), step(_step) {}
    };
    queue<node> que;
    int vis[maxn][maxn];
    char mp[maxn][maxn];
    int pre[10000000];
    int main() {
        int n, m, a, b;
        int p_x, p_y;
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; ++i) {
            scanf("%s", &mp[i]);
        }
    
        // 又是一套初始化
        memset(vis, 0, sizeof(vis));
        int ans, count = 0, an_x, an_y;
        scanf("%d %d", &a, &b);
        for (int i = 0; i < a;i++)
        {
            scanf("%d %d", &p_x, &p_y);
            if(mp[p_x-1][p_y-1] == '#')
                count++;
            else
                mp[p_x - 1][p_y - 1] = 'P';
        }
        if(count == a){
            printf("Cruel game\n");
            return 0;
        }
        while(b--)
        {
            scanf("%d %d", &an_x, &an_y);
            if(mp[an_x - 1][an_y - 1] == '#')
                ;
            else if(mp[an_x - 1][an_y - 1] == 'P'){
                printf("0\n%d %d\n", an_x, an_y);
                return 0;
            }
            else{
                que.push(node(an_x - 1, an_y - 1, 0));
                vis[an_x-1][an_y-1] = 1;
            }
        }
        int end_x, end_y, flag = 0,t;
        while (!que.empty()) {
            node tmp = que.front();//tmp为取出来的待处理的队首struct node类型的元素
            que.pop();
    
            if (mp[tmp.x][tmp.y] == 'P') {
                ans = tmp.step;
                end_x = tmp.x;
                end_y = tmp.y;
                flag = 1;
                break;
            }
    
            for (int i = 0; i < 4; ++i) {
                int x = tmp.x + dx[i], y = tmp.y + dy[i];
                if (x < 0 || x >= n || y < 0 || y >= m || mp[x][y] == '#' || vis[x][y] == 1) {
                    continue;
                }
                vis[x][y] = 1;
                pre[x * 10000 + y] = tmp.x * 10000 + tmp.y;
                que.push(node(x, y, tmp.step + 1));
                
            }
        }
        if(flag){
            printf("%d\n", ans);
            while(ans-->=0){
                printf("%d %d\n", end_x+1, end_y+1);
                t = pre[end_x * 10000 + end_y] / 10000;
                end_y = pre[end_x * 10000 + end_y] % 10000;
                end_x = t;
            }
        }
        else{
            printf("Peaceful world\n");
            return 0;
        }
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTIwNzE3NQ_size_16_color_FFFFFF_t_70]: /images/20220402/e343fb8504d44e3ba24275c0d10da96b.png