https://leetcode.com/problems/cat-and-mouse/

We can present every state of the game with a tuple (m, c, t) where m is the current position of the mouse, c is the current position of the cat, turn is 0 if it is the mouse’s turn and 1 if it is the cat’s turn to move.

All states of the game form a “game graph”. It is a directed graph and can contain cycles.

Unlike other games whose states form a “game tree”, for this kind of game we cannot simply apply DFS (DP with memoization) to figure out the WIN/LOSE/DRAW outcome of each state. Also, games with DRAW states are also not kind of problems I have usually worked with.

My solution is:

1. Discard DRAW altogether, the outcome is either WIN, LOSE or UNKNOWN.
2. We start from states with known outcomes (WIN/LOSE) and use these states to update other UNKNOWN states using the following rules:
   • For any UNKNOWN states s. If is is the mouse’s turn:
     • If s connects to a WIN state, it is a WIN state, otherwise:
     • If s connects to an UNKNOWN state, it continues to be an UNKNOWN state. Otherwise, it is a LOSE state.
   • If it is the cat’s turn to move:
     • If s connects to a LOSE state, it is a LOSE state, otherwise:
     • If s connects to an UNKNOWN state, it continues to be an UNKNOWN state. Otherwise, it is a WIN state.
3. After step 2, some UNKNOWN states will change to WIN/LOSE. Keep repeating step 2-3 until no new change can be made.
4. Finally, UNKNOWN states are considered DRAW.

Code:

#define UNKNOWN 0
#define WIN 1
#define LOSE 2

class Solution {
public:
    vector<vector<int>> edges;
    int outcome[55][55][2];

    bool cal(int m, int c, int t) {
        if (t == 0) {
            for (const int& i : edges[m]) {
                if (outcome[i][c][1] == WIN) {
                    outcome[m][c][0] = WIN;
                    return true;
                }
            }
            for (const int& i : edges[m]) {
                if (outcome[i][c][1] == UNKNOWN) {
                    outcome[m][c][0] = UNKNOWN;
                    return false;
                }
            }
            outcome[m][c][0] = LOSE;
            return true;
        }
        else {
            for (const int& i : edges[c]) if (i != 0) {
                if (outcome[m][i][0] == LOSE) {
                    outcome[m][c][1] = LOSE;
                    return true;
                }
            }
            for (const int& i : edges[c]) if (i != 0) {
                if (outcome[m][i][0] == UNKNOWN) {
                    outcome[m][c][1] = UNKNOWN;
                    return false;
                }
            }
            outcome[m][c][1] = WIN;
            return true;
        }
    }

    int catMouseGame(vector<vector<int>>& graph) {
        edges = graph;

        int n = graph.size();
        memset(outcome, 0, sizeof(outcome));

        for (int m = 0; m < n; ++m) {
            for (int c = 1; c < n; ++c) {
                for (int t = 0; t < 2; ++t) {
                    if (m == c) outcome[m][c][t] = LOSE;
                    else if (m == 0) outcome[m][c][t] = WIN;
                }
            }
        }

        bool stop = false;
        while (!stop) {
            stop = true;
            for (int m = 0; m < n; ++m) {
                for (int c = 0; c < n; ++c) {
                    for (int t = 0; t < 2; ++t) {
                        if (outcome[m][c][t] != UNKNOWN) continue;
                        if (cal(m, c, t)) {
                            stop = false;
                        }
                    }
                }
            }
        }

        return outcome[1][2][0];
    }
};