LeetCode

Editorial: LeetCode 1728 Cat and Mouse II

Editorial: LeetCode 1728 Cat and Mouse II

https://leetcode.com/problems/cat-and-mouse-ii/ from Google

Thinking process:

This is really a hard problem. Basically there is no quick way to figure out if mouse can win or not. The only thing we can do is to exhausted search all seach space. In the problem statement says If Mouse cannot get to the food within 1000 turns, Cat wins, so it seems like we need to search 1000 turns to make sure if cat wins or not?

The main trick for this problem is that we don’t need to search 1000 turns. Let’s assume the cat and the mouse are at whatever position in the grid, and the row x col is 64. Then, after 64*2 = 128 turns, they should be able to go whatever place they want. This is because if we assume their jump length to be 1 (the smallest), they’ll need at most 64 jumps to cover the whole grid, and they both need 64 turns so the total turn is 128.

With this, we only need to search 128 deeper. We use a dp array to store the solution if we know who will win. If the turn is more than 128, mouse lose. We use 1 to mean mouse win, and 0 to mean mouse lose.

Finally, in mouse’s turn, we default the status to mouse lose, and mouse can win once it finds one way to win. Same thing happens in cat’s turn, we default the status to cat lose (mouse win), and cat can win once it finds one way to win. This is the play optimally means in the problem statement. Both cat and mouse will only pick the way they can win.

Here is the code.

 1class Solution {
 2public:
 3    vector<int> cat;
 4    vector<int> mouse;
 5    vector<int> food;
 6    int R, C;
 7    int maxTurn;
 8    int dir[5] = {1, 0, -1, 0, 1};
 9    int dp[140][8][8][8][8];
10    int CJ, MJ;
11    vector<string> G;
12    int dfs(int turn, int m0, int m1, int c0, int c1) {
13        if (turn >= maxTurn) return 0;
14        if (dp[turn][m0][m1][c0][c1] != -1) return dp[turn][m0][m1][c0][c1];
15        int ret = (turn%2) == 0 ? 0 : 1;
16        if ((turn%2) == 0) { // mouse
17            if (m0 == food[0] and m1 == food[1]) ret = 1;
18            else {
19                for (int i=0; i<4 and ret != 1; i++) {
20                    for (int j=0; j<MJ+1; j++) {
21                        if (i != 0 and j == 0) continue;
22                        int x = m0 + j*dir[i];
23                        int y = m1 + j*dir[i+1];
24                        if (x < 0 or x >= R or y < 0 or y >= C or G[x][y] == '#') break;
25                        if (x == c0 and y == c1) continue;
26                        if (dfs(turn+1, x, y, c0, c1)) {
27                            ret = 1;
28                            break;
29                        }
30                    }
31                }
32            }
33        } else { // cat
34            if (c0 == food[0] and c1 == food[1]) ret = 0;
35            else if (m0 == food[0] and m1 == food[1]) ret = 1;
36            else {
37                for (int i=0; i<4 and ret != 0; i++) {
38                    for (int j=0; j<CJ+1; j++) {
39                        if (i != 0 and j == 0) continue;
40                        int x = c0 + j*dir[i];
41                        int y = c1 + j*dir[i+1];
42                        if (x < 0 or x >= R or y < 0 or y >= C or G[x][y] == '#') break;
43                        if (x == m0 and y == m1) {
44                            ret = 0; break;
45                        }
46                        if (dfs(turn+1, m0, m1, x, y) == 0) {
47                            ret = 0; break;
48                        }
49                    }
50                }
51            }
52        }
53        return dp[turn][m0][m1][c0][c1] = ret;
54    }
55    bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
56        cat.resize(2); mouse.resize(2); food.resize(2);
57        CJ = catJump; MJ = mouseJump;
58        G = grid; R = grid.size(); C = grid[0].size();
59        memset(dp, -1, sizeof(dp));
60        maxTurn = 2*R*C;
61        int R = grid.size(), C = grid[0].size();
62        for (int i=0; i<R; i++) {
63            for (int j=0; j<C; j++) {
64                if (grid[i][j] == 'C') cat[0] = i, cat[1] = j;
65                else if (grid[i][j] == 'M') mouse[0] = i, mouse[1] = j;
66                else if (grid[i][j] == 'F') food[0] = i, food[1] = j;
67            }
68        }
69        return dfs(0, mouse[0], mouse[1], cat[0], cat[1]);
70    }
71};
comments powered by Disqus