Cat and Mouse LeetCode solution in C++

1
class Solution {
2
 public:
3
  int catMouseGame(vector<vector<int>> &graph) {
4
    int N = graph.size();
5
    vector<vector<int>> dp[2];
6
    vector<vector<int>> outdegree[2];
7
    queue<vector<int>> q; // q of {turn, mouse position, cat position} for topological sort
8

9
    dp[0] = vector<vector<int>>(N, vector<int>(N));
10
    dp[1] = vector<vector<int>>(N, vector<int>(N));
11
    outdegree[0] = vector<vector<int>>(N, vector<int>(N));
12
    outdegree[1] = vector<vector<int>>(N, vector<int>(N));
13

14
    // init dp and queue
15
    for (int j = 0; j < N; ++j) {
16
      dp[0][0][j] = dp[1][0][j] = 1;
17
      q.push({0, 0, j});
18
      q.push({1, 0, j});
19
    }
20
    for (int j = 1; j < N; ++j) {
21
      dp[0][j][j] = dp[1][j][j] = 2;
22
      q.push({0, j, j});
23
      q.push({1, j, j});
24
    }
25
    // init outdegree
26
    for (int i = 0; i < N; ++i) {
27
      for (int j = 1; j < N; ++j) {
28
        outdegree[0][i][j] = graph[i].size();
29
        outdegree[1][i][j] = graph[j].size();
30
      }
31
    }
32
    for (auto &v : graph[0]) {
33
      for (int i = 0; i < N; ++i) {
34
        outdegree[1][i][v]--;
35
      }
36
    }
37
    // run the topological sort from queue
38
    while (q.size()) {
39
      auto turn = q.front()[0];
40
      auto mouse = q.front()[1];
41
      auto cat = q.front()[2];
42
      q.pop();
43

44
      if (turn == 0 && mouse == 1 && cat == 2) {
45
        // the result has been inferenced
46
        break;
47
      }
48

49
      if (turn == 0) { // mouse's turn
50
        // v is the prev position of cat
51
        for (auto &v : graph[cat]) {
52
          if (v == 0) {
53
            continue;
54
          }
55

56
          if (dp[1][mouse][v] > 0) {
57
            continue;
58
          }
59

60
          if (dp[turn][mouse][cat] == 2) {
61
            // cat wants to move from v to `cat` position, and thus cat wins
62
            dp[1][mouse][v] = 2;
63
            q.push({1, mouse, v});
64
            continue;
65
          }
66

67
          outdegree[1][mouse][v]--;
68
          if (outdegree[1][mouse][v] == 0) {
69
            dp[1][mouse][v] = 1;
70
            q.push({1, mouse, v});
71
          }
72
        }
73
      } else { // cat's turn
74
        // v is the prev position of mouse
75
        for (auto &v : graph[mouse]) {
76
          if (dp[0][v][cat] > 0) {
77
            continue;
78
          }
79

80
          if (dp[turn][mouse][cat] == 1) {
81
            // mouse wants to move from v to `mouse` position and thus mouse
82
            // wins
83
            dp[0][v][cat] = 1;
84
            q.push({0, v, cat});
85
            continue;
86
          }
87

88
          outdegree[0][v][cat]--;
89
          if (outdegree[0][v][cat] == 0) {
90
            dp[0][v][cat] = 2;
91
            q.push({0, v, cat});
92
          }
93
        }
94
      }
95
    }
96

97
    return dp[0][1][2];
98
  }
99
};