AcWing：177. 噩梦（bfs）

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

const int maxn = 1e3+7;

struct node {
    int x, y, step;
};

char Map[maxn][maxn];
int dir[4][2] = {0, -1, 0, 1, -1, 0, 1, 0};
int n, m;

bool check(int x, int y) {
    if(x <= 0 || x > n || y <= 0 || y > m) {
        return false;
    }
    return true;
}

int bfs() {
    queue<node> girl, boy, ghost;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(Map[i][j] == ‘M‘) {
                boy.push((node){i, j, 0});
            } else if(Map[i][j] == ‘G‘) {
                girl.push((node){i, j, 0});
            } else if(Map[i][j] == ‘Z‘) {
                ghost.push((node){i, j, 0});
            }
        }
    }
    for(int i = 1; i <= 100005; i++) {      //枚举来遍历这些时间
        int tmp = ghost.front().step + 2;   //限制了移动的距离
        while(!ghost.empty() && ghost.front().step < tmp) { 
            node now = ghost.front();
            ghost.pop();
            for(int j = 0; j < 4; j++) {
                int tx = now.x + dir[j][0];
                int ty = now.y + dir[j][1];
                if(check(tx, ty) && Map[tx][ty] != ‘#‘) {
                    ghost.push((node){tx, ty, now.step + 1});
                    Map[tx][ty] = ‘#‘;
                    Map[now.x][now.y] = ‘#‘;
                }
            }
        }
        tmp = boy.front().step + 3;
        while(!boy.empty() && boy.front().step < tmp) {
            node now = boy.front();
            boy.pop();
            for(int j = 0; j < 4; j++) {
                int tx = now.x + dir[j][0];
                int ty = now.y + dir[j][1];
                if(check(tx, ty) && Map[tx][ty] != ‘#‘) {
                    if(Map[tx][ty] == ‘.‘) {
                        boy.push((node){tx, ty, now.step + 1});
                        Map[tx][ty] = ‘M‘;
                        Map[now.x][now.y] = ‘X‘;
                    } else if(Map[tx][ty] == ‘G‘) {
                        return i;
                    }
                }
            }
        }
        tmp = girl.front().step + 1;
        while(!girl.empty() && girl.front().step < tmp) {
            node now = girl.front();
            girl.pop();
            for(int j = 0; j < 4; j++) {
                int tx = now.x + dir[j][0];
                int ty = now.y + dir[j][1];
                if(check(tx, ty) && Map[tx][ty] != ‘#‘) {
                    if(Map[tx][ty] == ‘.‘) {
                        girl.push((node){tx, ty, now.step + 1});
                        Map[tx][ty] = ‘G‘;
                        Map[now.x][now.y] = ‘X‘;
                    } else if(Map[tx][ty] == ‘M‘) {
                        return i;
                    }
                }
            }
        }
           
    }
    return -1;
}

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d", &n, &m);
        for(int i = 1; i <= n; i++) {
            getchar();
            for(int j = 1; j <= m; j++) {
                scanf("%c", &Map[i][j]);
            }
        }
        printf("%d\n", bfs());
    }
    return 0;
}