Skip to content

1728. Cat and Mouse II 👍

  • Time: $O(m^3n^3 \cdot (m + n))$
  • Space: $O(m^3n^3)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
class Solution {
 public:
  bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
    const int m = grid.size();
    const int n = grid[0].size();
    int nFloors = 0;
    int cat;    // cat's position
    int mouse;  // mouse's position

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] != '#')
          ++nFloors;
        if (grid[i][j] == 'C')
          cat = hash(i, j, n);
        else if (grid[i][j] == 'M')
          mouse = hash(i, j, n);
      }

    vector<vector<vector<int>>> mem(
        m * n, vector<vector<int>>(m * n, vector<int>(nFloors * 2, -1)));
    return canMouseWin(grid, cat, mouse, 0, catJump, mouseJump, m, n, nFloors,
                       mem);
  }

 private:
  static constexpr int kDirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

  // Returns true if the mouse can win, where the cat is on (i / 8, i % 8), the
  // mouse is on (j / 8, j % 8), and the turns is k.
  bool canMouseWin(const vector<string>& grid, int cat, int mouse, int turn,
                   const int& catJump, const int& mouseJump, const int& m,
                   const int& n, const int& nFloors,
                   vector<vector<vector<int>>>& mem) {
    // We already search the whole touchable grid.
    if (turn == nFloors * 2)
      return false;
    if (mem[cat][mouse][turn] != -1)
      return mem[cat][mouse][turn];

    if (turn % 2 == 0) {
      // the mouse's turn
      const int i = mouse / n;
      const int j = mouse % n;
      for (const auto& [dx, dy] : kDirs) {
        for (int jump = 0; jump <= mouseJump; ++jump) {
          const int x = i + dx * jump;
          const int y = j + dy * jump;
          if (x < 0 || x == m || y < 0 || y == n)
            break;
          if (grid[x][y] == '#')
            break;
          // The mouse eats the food, so the mouse wins.
          if (grid[x][y] == 'F')
            return mem[cat][mouse][turn] = true;
          if (canMouseWin(grid, cat, hash(x, y, n), turn + 1, catJump,
                          mouseJump, m, n, nFloors, mem))
            return mem[cat][mouse][turn] = true;
        }
      }
      // The mouse can't win, so the mouse loses.
      return mem[cat][mouse][turn] = false;
    } else {
      // the cat's turn
      const int i = cat / n;
      const int j = cat % n;
      for (const auto& [dx, dy] : kDirs) {
        for (int jump = 0; jump <= catJump; ++jump) {
          const int x = i + dx * jump;
          const int y = j + dy * jump;
          if (x < 0 || x == m || y < 0 || y == n)
            break;
          if (grid[x][y] == '#')
            break;
          // The cat eats the food, so the mouse loses.
          if (grid[x][y] == 'F')
            return mem[cat][mouse][turn] = false;
          const int nextCat = hash(x, y, n);
          // The cat catches the mouse, so the mouse loses.
          if (nextCat == mouse)
            return mem[cat][mouse][turn] = false;
          if (!canMouseWin(grid, nextCat, mouse, turn + 1, catJump, mouseJump,
                           m, n, nFloors, mem))
            return mem[cat][mouse][turn] = false;
        }
      }
      // The cat can't win, so the mouse wins.
      return mem[cat][mouse][turn] = true;
    }
  }

  int hash(int i, int j, int n) {
    return i * n + j;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class Solution {
  public boolean canMouseWin(String[] grid, int catJump, int mouseJump) {
    final int m = grid.length;
    final int n = grid[0].length();
    int nFloors = 0;
    int cat = 0;   // cat's position
    int mouse = 0; // mouse's position

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        if (grid[i].charAt(j) != '#')
          ++nFloors;
        if (grid[i].charAt(j) == 'C')
          cat = hash(i, j, n);
        else if (grid[i].charAt(j) == 'M')
          mouse = hash(i, j, n);
      }

    Boolean[][][] mem = new Boolean[m * n][m * n][nFloors * 2];
    return canMouseWin(grid, cat, mouse, 0, catJump, mouseJump, m, n, nFloors, mem);
  }

  private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

  // Returns true if the mouse can win, where the cat is on (i / 8, i % 8), the
  // mouse is on (j / 8, j % 8), and the turns is k.
  private boolean canMouseWin(String[] grid, int cat, int mouse, int turn, int catJump,
                              int mouseJump, int m, int n, int nFloors, Boolean[][][] mem) {
    // We already search the whole touchable grid.
    if (turn == nFloors * 2)
      return false;
    if (mem[cat][mouse][turn] != null)
      return mem[cat][mouse][turn];

    if (turn % 2 == 0) {
      // the mouse's turn
      int i = mouse / n;
      int j = mouse % n;
      for (int[] dir : DIRS) {
        for (int jump = 0; jump <= mouseJump; ++jump) {
          int x = i + dir[0] * jump;
          int y = j + dir[1] * jump;
          if (x < 0 || x == m || y < 0 || y == n)
            break;
          if (grid[x].charAt(y) == '#')
            break;
          // The mouse eats the food, so the mouse wins.
          if (grid[x].charAt(y) == 'F')
            return mem[cat][mouse][turn] = true;
          if (canMouseWin(grid, cat, hash(x, y, n), turn + 1, catJump, mouseJump, m, n, nFloors,
                          mem))
            return mem[cat][mouse][turn] = true;
        }
      }
      // The mouse can't win, so the mouse loses.
      return mem[cat][mouse][turn] = false;
    } else {
      // the cat's turn
      final int i = cat / n;
      final int j = cat % n;
      for (int[] dir : DIRS)
        for (int jump = 0; jump <= catJump; ++jump) {
          final int x = i + dir[0] * jump;
          final int y = j + dir[1] * jump;
          if (x < 0 || x == m || y < 0 || y == n)
            break;
          if (grid[x].charAt(y) == '#')
            break;
          // The cat eats the food, so the mouse loses.
          if (grid[x].charAt(y) == 'F')
            return mem[cat][mouse][turn] = false;
          final int nextCat = hash(x, y, n);
          if (nextCat == mouse)
            return mem[cat][mouse][turn] = false;
          if (!canMouseWin(grid, nextCat, mouse, turn + 1, catJump, mouseJump, m, n, nFloors, mem))
            return mem[cat][mouse][turn] = false;
        }
      // The cat can't win, so the mouse wins.
      return mem[cat][mouse][turn] = true;
    }
  }

  private int hash(int i, int j, int n) {
    return i * n + j;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Solution:
  def canMouseWin(self, grid: list[str], catJump: int, mouseJump: int) -> bool:
    DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))
    m = len(grid)
    n = len(grid[0])
    nFloors = 0
    cat = 0  # cat's position
    mouse = 0  # mouse's position

    def hash(i: int, j: int) -> int:
      return i * n + j

    for i in range(m):
      for j in range(n):
        if grid[i][j] != '#':
          nFloors += 1
        if grid[i][j] == 'C':
          cat = hash(i, j)
        elif grid[i][j] == 'M':
          mouse = hash(i, j)

    @functools.lru_cache(None)
    def dp(cat: int, mouse: int, turn: int) -> bool:
      """
      Returns True if the mouse can win, where the cat is on (i / 8, i % 8), the
      mouse is on (j / 8, j % 8), and the turns is k.
      """
      # We already search the whole touchable grid.
      if turn == nFloors * 2:
        return False

      if turn % 2 == 0:
        # the mouse's turn
        i = mouse // n
        j = mouse % n
        for dx, dy in DIRS:
          for jump in range(mouseJump + 1):
            x = i + dx * jump
            y = j + dy * jump
            if x < 0 or x == m or y < 0 or y == n:
              break
            if grid[x][y] == '#':
              break
            # The mouse eats the food, so the mouse wins.
            if grid[x][y] == 'F':
              return True
            if dp(cat, hash(x, y), turn + 1):
              return True
        # The mouse can't win, so the mouse loses.
        return False
      else:
        # the cat's turn
        i = cat // n
        j = cat % n
        for dx, dy in DIRS:
          for jump in range(catJump + 1):
            x = i + dx * jump
            y = j + dy * jump
            if x < 0 or x == m or y < 0 or y == n:
              break
            if grid[x][y] == '#':
              break
            # The cat eats the food, so the mouse loses.
            if grid[x][y] == 'F':
              return False
            nextCat = hash(x, y)
            # The cat catches the mouse, so the mouse loses.
            if nextCat == mouse:
              return False
            if not dp(nextCat, mouse, turn + 1):
              return False
        # The cat can't win, so the mouse wins.
        return True

    return dp(cat, mouse, 0)