题意

传送门 LeeCode 913 猫和老鼠

题解

任意图上博弈，可参考 Games on arbitrary graphs。对于此类博弈，胜负态与博弈者相关。

简单而言，将博弈双方的状态转移 $(i,u,v)$ 建反图，其中 $i$ 代表当前准备出手的一方，$u,v$ 分别为博弈双方所在节点。在反图上没有入边的节点一定为某一方的获胜态；那么从这样的节点，按照一般胜负态转移的规则，对其前驱状态进行胜负态判断。最终，不能明确胜负态的状态为平局态。

class Solution
{static const int MAXN = 55;public:int in[2][MAXN], mem[2][MAXN][MAXN];int cnt[2][MAXN][MAXN];vector<vector<int>> G;bool conf(int u, int v) { return u == v || u == 0 || v == 0; }void dfs(int k, int u, int v, int res){mem[k][u][v] = res;int k2 = k ^ 1;if (k == 0){for (auto &w : G[v])if (!conf(u, w) && mem[k2][u][w] == -1){bool ok = 0;if (k != res)ok = 1;else if (++cnt[k2][u][w] == in[k2][w])ok = 1;if (ok)dfs(k2, u, w, res);}}else{for (auto &w : G[u])if (!conf(w, v) && mem[k2][w][v] == -1){bool ok = 0;if (k != res)ok = 1;else if (++cnt[k2][w][v] == in[k2][w])ok = 1;if (ok)dfs(k2, w, v, res);}}}int catMouseGame(vector<vector<int>> &graph){G = graph;int n = G.size();memset(in, 0, sizeof(in));memset(mem, -1, sizeof(mem));memset(cnt, 0, sizeof(cnt));for (int u = 1; u < n; ++u){in[0][u] = in[1][u] = G[u].size();for (auto &w : G[u])if (w == 0)--in[1][u];}for (int u = 1; u < n; ++u)for (int k = 0; k < 2; ++k)dfs(k, 0, u, 0), dfs(k, u, u, 1);return mem[0][1][2] == -1 ? 0 : mem[0][1][2] + 1;}
};