【Leetcode 913】【Hard】Cat and Mouse 博弈论-蒲公英云

描述

913. Cat and Mouse

Hard

A game on an undirected graph is played by two players, Mouse and Cat, who alternate turns.

The graph is given as follows: graph[a] is a list of all nodes b such that ab is an edge of the graph.

Mouse starts at node 1 and goes first, Cat starts at node 2 and goes second, and there is a Hole at node 0.

During each player’s turn, they must travel along one edge of the graph that meets where they are. For example, if the Mouse is at node 1, it must travel to any node in graph[1].

Additionally, it is not allowed for the Cat to travel to the Hole (node 0.)

Then, the game can end in 3 ways:

If ever the Cat occupies the same node as the Mouse, the Cat wins.
If ever the Mouse reaches the Hole, the Mouse wins.
If ever a position is repeated (ie. the players are in the same position as a previous turn, and it is the same player’s turn to move), the game is a draw.

Given a graph, and assuming both players play optimally, return 1 if the game is won by Mouse, 2 if the game is won by Cat, and 0 if the game is a draw.

Example 1:

Input: [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]

Output: 0

Explanation:

4—-3—-1

| |

2—-5

\ /

Note:

3 <= graph.length <= 50
It is guaranteed that graph[1] is non-empty.
It is guaranteed that graph[2] contains a non-zero element.

题解

本题是一个猫和老鼠的追逐博弈，题目的限制条件有：

1.老鼠先发，猫后走，轮流运动（而且必须运动，不能守株待兔）

2.老鼠初始在位置1，猫在位置2

3.猫和老鼠在同一位置，则猫胜；老鼠进洞则鼠胜

4.猫任何时候不能进洞

5.图是连通的

对本题的错误解法可能有：

1.从开始状态BFS模拟过程，直至有一方会输，然而一个状态可以有N条邻接的路可走，完全可以选一个不会输的路，所以这么解不行；比如对邻接图

0—2— 4— 5

 |           |
 3-- -----1

老鼠开始的模拟就会有一条输的路，但是它可以走另外一条路达成平局。

2.在1的基础上，考虑每次的所有选择，如果至少有一条成功，就不会输。这个解法也是错的，因为每一条路其实都不能提前确定最后的结果，即使当前选择了一条可能成功的路，也可能在后面失败，由于博弈的存在，当前节点（用m，c，turn表示）扩展到后面，其结果还要由另外一方来决定。这样，即使有成功的机会，也要往开始回溯，看是否能达到这样的状态。这样跟开始的顺推思路是矛盾的。

由于这种考虑，要用逆推法进行BFS回溯。从最后的结果来说，(m,c,turn)=(0,i,turn)的时候为mouse胜，(m,c,turn)=(i,i,turn)的时候为cat胜。

逆推的时候要注意博弈的思路，若当前状态下，A为胜，则上一步B不会走这条路，当然上一步B的选择自动减少1；若A为负，则上一步B必然会选择这条路。当上一步B的选择数为0，说明B必败。非平局的结果都被队列保存起来。

代码

#include <bits/stdc++.h>
using namespace std;
typedef struct State {
    int m, c, turn;
    State(int _m, int _c, int _turn):
    m(_m), c(_c), turn(_turn) {}
} State;
class Solution {
public:
    enum winState {
        DRAW,
        WIN,
        LOST
    };
    enum turnState {
        MOUSE,
        CAT
    };
    int catMouseGame(vector<vector<int> >& graph) {
        int n = graph.size();
        vector<vector<vector<int> > > res(n,
            vector<vector<int> >(n, vector<int>(2, 0)));
        vector<vector<vector<int> > > child(n,
            vector<vector<int> >(n, vector<int>(2, 0)));
        int m, c;
        for (int i = 0; i < n; i++) {
            // if mouse is in hole, for mouse it wins
            res[0][i][MOUSE] = WIN;
            res[0][i][CAT] = LOST;
            if (i) {
                res[i][i][MOUSE] = LOST;
                res[i][i][CAT] = WIN;
            }
            for (int j = 0; j < n; j++) {
                // number of next possible positions from current state
                child[i][j][MOUSE] = graph[i].size();
                child[i][j][CAT] = graph[j].size();
                for (auto& k: graph[j]) {
                    if (k == 0) {
                        child[i][j][CAT]--;
                        break;
                    }
                }
            }
        }
        queue<State> q;
        for (m = 0; m < n; m++) {
            for (c = 0; c < n; c++) {
                for (int turn = 0; turn <= 1; turn++) {
                    if (res[m][c][turn] != DRAW) {
                        // add states that will lead to result state
                        q.push({m, c, turn});
                    }
                }
            }
        }
        while (!q.empty()) {
            State f = q.front();
            q.pop();
            int prev_turn = 1 - f.turn;
            int curState = res[f.m][f.c][f.turn];
            int prev_m, prev_c;
            int adj = prev_turn == CAT ? f.c : f.m;
            // visit adj positions that are not yet expanded
            for (auto& v: graph[adj]) {
                prev_m = prev_turn == MOUSE ? v : f.m;
                prev_c = prev_turn == CAT ? v : f.c;
                if (!prev_c) continue;
                if (res[prev_m][prev_c][prev_turn] != DRAW) continue;
                if (curState == LOST) {
                    res[prev_m][prev_c][prev_turn] = WIN;
                    q.push({prev_m, prev_c, prev_turn});
                } else {
                    child[prev_m][prev_c][prev_turn]--;
                    if (!child[prev_m][prev_c][prev_turn])
                    {
                        res[prev_m][prev_c][prev_turn] = LOST;
                        q.push({prev_m, prev_c, prev_turn});
                    }
                }
            }
        }
        return res[1][2][MOUSE];
    }
};

测试用例

int main() {
    Solution sol;
    int n, m;
    while (cin >> n) {
        if (n < 3) {
            cout << "error input\n";
            continue;
        }
        vector<vector<int> > graph(n);
        int u, v;
        int edge;
        cin >> edge;
        for (int i = 0; i < edge; i++) {
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        cout << sol.catMouseGame(graph) << endl;
    }
    return 0;
}
In:
3
2
0 1
1 2
Out:
1
In:
6
7
0 2
0 5
2 5
4 3
2 4
3 5
1 3
Out:
0
In:
5
5
0 3
1 3
2 3
1 4
2 4
Out:
2