Cat and Mouse II LeetCode solution in C++

1
class Solution {
2
 public:
3
  bool canMouseWin(vector<string> &grid, int catJump, int mouseJump) {
4
    m = grid.size();
5
    n = grid[0].size();
6
    int cat;   // cat's position
7
    int mouse; // mouse's position
8

9
    for (int i = 0; i < m; ++i)
10
      for (int j = 0; j < n; ++j) {
11
        if (grid[i][j] != '#') ++nFloors;
12
        if (grid[i][j] == 'C')
13
          cat = hash(i, j);
14
        else if (grid[i][j] == 'M')
15
          mouse = hash(i, j);
16
      }
17

18
    // dp[i][j][k] := true if mouse can win w/
19
    // Cat on (i / 8, i % 8), mouse on (j / 8, j % 8), and turns = k
20
    dp.resize(m * n, vector<vector<int>>(m * n, vector<int>(nFloors * 2, -1)));
21
    return canMouseWin(grid, cat, mouse, 0, catJump, mouseJump);
22
  }
23

24
 private:
25
  const vector<int> dirs{0, 1, 0, -1, 0};
26
  int m;
27
  int n;
28
  int nFloors = 0;
29
  vector<vector<vector<int>>> dp;
30

31
  bool canMouseWin(const vector<string> &grid, int cat, int mouse, int turn, const int &catJump,
32
                   const int &mouseJump) {
33
    // We already search whole touchable grid
34
    if (turn == nFloors * 2) return false;
35
    if (dp[cat][mouse][turn] != -1) return dp[cat][mouse][turn];
36

37
    if (turn % 2 == 0) {
38
      // mouse's turn
39
      const int i = mouse / n;
40
      const int j = mouse % n;
41
      for (int k = 0; k < 4; ++k) {
42
        for (int jump = 0; jump <= mouseJump; ++jump) {
43
          const int x = i + dirs[k] * jump;
44
          const int y = j + dirs[k + 1] * jump;
45
          if (x < 0 || x == m || y < 0 || y == n) break;
46
          if (grid[x][y] == '#') break;
47
          if (grid[x][y] == 'F') // Mouse eats the food, so mouse win
48
            return dp[cat][mouse][turn] = true;
49
          if (canMouseWin(grid, cat, hash(x, y), turn + 1, catJump, mouseJump))
50
            return dp[cat][mouse][turn] = true;
51
        }
52
      }
53
      // Mouse can't win, so mouse lose
54
      return dp[cat][mouse][turn] = false;
55
    } else {
56
      // cat's turn
57
      const int i = cat / n;
58
      const int j = cat % n;
59
      for (int k = 0; k < 4; ++k) {
60
        for (int jump = 0; jump <= catJump; ++jump) {
61
          const int x = i + dirs[k] * jump;
62
          const int y = j + dirs[k + 1] * jump;
63
          if (x < 0 || x == m || y < 0 || y == n) break;
64
          if (grid[x][y] == '#') break;
65
          if (grid[x][y] == 'F') // Cat eats the food, so mouse lose
66
            return dp[cat][mouse][turn] = false;
67
          const int nextCat = hash(x, y);
68
          if (nextCat == mouse) // Cat catches mouse, so mouse lose
69
            return dp[cat][mouse][turn] = false;
70
          if (!canMouseWin(grid, nextCat, mouse, turn + 1, catJump, mouseJump))
71
            return dp[cat][mouse][turn] = false;
72
        }
73
      }
74
      // Cat can't win, so mouse win
75
      return dp[cat][mouse][turn] = true;
76
    }
77
  }
78

79
  int hash(int i, int j) {
80
    return i * n + j;
81
  }
82
};