【Leetcode 913】【Hard】Cat and Mouse 博弈论

小咪咪 2023-06-03 15:54 6阅读 0赞

## 描述 ##

**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:**

1.  3 <= graph.length <= 50
2.  It is guaranteed that graph\[1\] is non-empty. 
3.  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

**References:**

**[https://leetcode.com/problems/cat-and-mouse/][https_leetcode.com_problems_cat-and-mouse]**

转载于:https://www.cnblogs.com/wangzming/p/11579770.html

[https_leetcode.com_problems_cat-and-mouse]: https://leetcode.com/problems/cat-and-mouse/