LeeCode 1728 任意图上博弈

题意

传送门 LeeCode 1728 猫和老鼠 II

题解

任意图上博弈，可参考 Games on arbitrary graphs。具体而言，将博弈双方位置加之先后手状态看作任意图上的一个节点，并根据状态转移建立反图。对于可以确定胜负态的节点，以其为起点，使用类似拓扑序更新的操作不断递推其余节点的状态。对于$n\times m$的方格，任意图博弈求解时间复杂度为$O((nm{)}^2\max (n,m))$。

#include <bits/stdc++.h>
using namespace std;

class Solution {
   public:
    bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
        int n = grid.size(), m = grid[0].size();
        int mx = -1, my = -1;
        int cx = -1, cy = -1;
        int fx = -1, fy = -1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                auto c = grid[i][j];
                if (c == 'M') {
                    mx = i, my = j;
                }
                if (c == 'C') {
                    cx = i, cy = j;
                }
                if (c == 'F') {
                    fx = i, fy = j;
                }
            }
        }
        const vector<int> dx = {0, 0, -1, 1};
        const vector<int> dy = {-1, 1, 0, 0};
        int pos_num = n * m;
        int state_num = pos_num * pos_num * 2;
        vector<vector<int>> g(state_num);
        auto get = [&](int u, int v, int who) {
            return u + v * pos_num + who * pos_num * pos_num;
        };
        auto judge = [&](int x, int y) {
            return 0 <= x && x < n && 0 <= y && y < m && grid[x][y] != '#';
        };
        auto ed = [&](int cv, int mv) {
            int fv = fx * m + fy;
            return cv == mv || cv == fv || mv == fv;
        };
        for (int cv = 0; cv < pos_num; ++cv) {
            for (int mv = 0; mv < pos_num; ++mv) {
                if (ed(cv, mv)) {
                    continue;
                }
                for (int who = 0; who < 2; ++who) {
                    int w = who == 0 ? cv : mv;
                    int sx = w / m, sy = w % m;
                    int lim = who == 0 ? catJump : mouseJump;
                    for (int k = 0; k < (int)dx.size(); ++k) {
                        int x = sx, y = sy;
                        for (int d = 0; d <= lim; ++d) {
                            if (!judge(x, y)) {
                                break;
                            }
                            if (who == 0) {
                                g[get(x * m + y, mv, who ^ 1)].push_back(get(cv, mv, who));
                            } else {
                                g[get(cv, x * m + y, who ^ 1)].push_back(get(cv, mv, who));
                            }
                            x += dx[k];
                            y += dy[k];
                        }
                    }
                }
            }
        }
        vector<int> indeg(state_num);
        for (int u = 0; u < state_num; ++u) {
            for (int v : g[u]) {
                indeg[v] += 1;
            }
        }
        vector<int> win(state_num, -1);
        function<void(int)> dfs = [&](int v) {
            for (int u : g[v]) {
                if (win[u] == -1) {
                    if (win[v] == 0) {
                        win[u] = 1;
                    } else {
                        indeg[u] -= 1;
                        if (indeg[u] == 0) {
                            win[u] = 0;
                        }
                    }
                    if (win[u] != -1) {
                        dfs(u);
                    }
                }
            }
        };
        for (int cv = 0; cv < pos_num; ++cv) {
            int x = cv / m, y = cv % m;
            if (judge(x, y)) {
                for (int who = 0; who < 2; ++who) {
                    int v = get(cv, cv, who);
                    win[v] = who ^ 1;
                    dfs(v);
                }
            }
        }
        for (int v = 0; v < pos_num; ++v) {
            int x = v / m, y = v % m;
            int f = fx * m + fy;
            if (judge(x, y) && v != f) {
                int u = get(f, v, 1);
                win[u] = 0;
                dfs(u);
                int w = get(v, f, 0);
                win[w] = 0;
                dfs(w);
            }
        }
        int res = win[get(cx * m + cy, mx * m + my, 1)];
        return res == 1;
    }
};