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
class Solution {
 public:
  bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
    m = grid.size();
    n = grid[0].size();
    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);
        else if (grid[i][j] == 'M')
          mouse = hash(i, j);
      }

    // dp[i][j][k] := 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 = k
    dp.resize(m * n, vector<vector<int>>(m * n, vector<int>(nFloors * 2, -1)));
    return canMouseWin(grid, cat, mouse, 0, catJump, mouseJump);
  }

 private:
  const vector<int> dirs{0, 1, 0, -1, 0};
  int m;
  int n;
  int nFloors = 0;
  vector<vector<vector<int>>> dp;

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

    if (turn % 2 == 0) {
      // the mouse's turn
      const int i = mouse / n;
      const int j = mouse % n;
      for (int k = 0; k < 4; ++k) {
        for (int jump = 0; jump <= mouseJump; ++jump) {
          const int x = i + dirs[k] * jump;
          const int y = j + dirs[k + 1] * 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 dp[cat][mouse][turn] = true;
          if (canMouseWin(grid, cat, hash(x, y), turn + 1, catJump, mouseJump))
            return dp[cat][mouse][turn] = true;
        }
      }
      // The mouse can't win, so the mouse loses.
      return dp[cat][mouse][turn] = false;
    } else {
      // the cat's turn
      const int i = cat / n;
      const int j = cat % n;
      for (int k = 0; k < 4; ++k) {
        for (int jump = 0; jump <= catJump; ++jump) {
          const int x = i + dirs[k] * jump;
          const int y = j + dirs[k + 1] * 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 dp[cat][mouse][turn] = false;
          const int nextCat = hash(x, y);
          // The cat catches the mouse, so the mouse loses.
          if (nextCat == mouse)
            return dp[cat][mouse][turn] = false;
          if (!canMouseWin(grid, nextCat, mouse, turn + 1, catJump, mouseJump))
            return dp[cat][mouse][turn] = false;
        }
      }
      // The cat can't win, so the mouse wins.
      return dp[cat][mouse][turn] = true;
    }
  }

  int hash(int i, int j) {
    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
87
88
89
class Solution {
  public boolean canMouseWin(String[] grid, int catJump, int mouseJump) {
    m = grid.length;
    n = grid[0].length();
    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);
        else if (grid[i].charAt(j) == 'M')
          mouse = hash(i, j);
      }

    // dp[i][j][k] := 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 = k
    dp = new Boolean[m * n][m * n][nFloors * 2];
    return canMouseWin(grid, cat, mouse, 0, catJump, mouseJump);
  }

  private static final int[] dirs = {0, 1, 0, -1, 0};
  private int m;
  private int n;
  private int nFloors = 0;
  private Boolean[][][] dp;

  private boolean canMouseWin(final String[] grid, int cat, int mouse, int turn, int catJump,
                              int mouseJump) {
    // We already search the whole touchable grid.
    if (turn == nFloors * 2)
      return false;
    if (dp[cat][mouse][turn] != null)
      return dp[cat][mouse][turn];

    if (turn % 2 == 0) {
      // the mouse's turn
      final int i = mouse / n;
      final int j = mouse % n;
      for (int k = 0; k < 4; ++k) {
        for (int jump = 0; jump <= mouseJump; ++jump) {
          final int x = i + dirs[k] * jump;
          final int y = j + dirs[k + 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 dp[cat][mouse][turn] = true;
          if (canMouseWin(grid, cat, hash(x, y), turn + 1, catJump, mouseJump))
            return dp[cat][mouse][turn] = true;
        }
      }
      // The mouse can't win, so the mouse loses.
      return dp[cat][mouse][turn] = false;
    } else {
      // the cat's turn
      final int i = cat / n;
      final int j = cat % n;
      for (int k = 0; k < 4; ++k) {
        for (int jump = 0; jump <= catJump; ++jump) {
          final int x = i + dirs[k] * jump;
          final int y = j + dirs[k + 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 dp[cat][mouse][turn] = false;
          final int nextCat = hash(x, y);
          if (nextCat == mouse) // The cat catches the mouse, so the mouse loses.
            return dp[cat][mouse][turn] = false;
          if (!canMouseWin(grid, nextCat, mouse, turn + 1, catJump, mouseJump))
            return dp[cat][mouse][turn] = false;
        }
      }
      // The cat can't win, so the mouse wins.
      return dp[cat][mouse][turn] = true;
    }
  }

  private int hash(int i, int j) {
    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, 0, -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 = 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 k in range(4):
          for jump in range(mouseJump + 1):
            x = i + dirs[k] * jump
            y = j + dirs[k + 1] * 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 k in range(4):
          for jump in range(catJump + 1):
            x = i + dirs[k] * jump
            y = j + dirs[k + 1] * 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)