Cat and Mouse II LeetCode solution in Python

1
class Solution:
2
    def canMouseWin(self, A: List[str], cj: int, mj: int) -> bool:
3
        # some helper functions:
4
        xy2i = lambda x, y: x * n + y
5
        i2xy = lambda i: (i // n, i % n)
6

7
        def adj_grid(x0, y0, jump=1):
8
            for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
9
                for step in range(jump):
10
                    x, y = x0 + (step + 1) * dx, y0 + (step + 1) * dy
11
                    if not (0 <= x < m and 0 <= y < n) or A[x][y] == "#":
12
                        break
13
                    yield x, y
14

15
        m, n, jps = len(A), len(A[0]), (mj, cj)
16
        fi = mi = ci = 0  # location of food, mouse, cat
17
        for i in range(m):
18
            for j in range(n):
19
                if A[i][j] == "C":
20
                    ci = xy2i(i, j)
21
                elif A[i][j] == "M":
22
                    mi = xy2i(i, j)
23
                elif A[i][j] == "F":
24
                    fi = xy2i(i, j)
25

26
        # BFS for unreachable food cases
27
        def reach_food(x, y):
28
            B = [list(row) for row in A]
29
            B[x][y] = "#"
30
            que = collections.deque([(x, y)])
31
            while que:
32
                for x, y in adj_grid(*que.popleft()):
33
                    if B[x][y] == "#":
34
                        continue
35
                    if B[x][y] == "F":
36
                        return True
37
                    B[x][y] = "#"
38
                    que.append((x, y))
39
            return False
40

41
        if not reach_food(*i2xy(mi)):
42
            return False
43
        elif not reach_food(*i2xy(ci)):
44
            return True
45

46
        # adjacent states counter
47
        adj = [[[0] * (m * n) for _ in range(m * n)] for _ in range(2)]
48
        for i0 in range(m * n):
49
            for k in (0, 1):
50
                i = [0, 0]
51
                i[k] = i0
52
                for x, y in adj_grid(*i2xy(i0), jps[k]):
53
                    adj[k][i[0]][i[1]] += 1
54
                i2 = i.copy()
55
                for i2[1 - k] in range(m * n):
56
                    adj[k][i2[0]][i2[1]] = adj[k][i[0]][i[1]]
57

58
        dp = [[[None] * (m * n) for _ in range(m * n)] for _ in range(2)]
59
        que1, que2 = (
60
            collections.deque(),
61
            collections.deque(),
62
        )  # que1 for decisive states, que2 for indecisive ones
63
        for i in range(m * n):
64
            x, y = i2xy(i)
65
            if A[x][y] == "#":
66
                continue
67
            if i != fi:
68
                dp[0][fi][i] = dp[1][fi][i] = True
69
                que1.append((1, fi, i))
70
                que2.append((0, fi, i))
71
            dp[0][i][fi] = dp[1][i][fi] = dp[0][i][i] = dp[1][i][i] = False
72
            que1.append((0, i, fi))
73
            que2.append((1, i, fi))
74
            que1.append((0, i, i))
75
            que2.append((1, i, i))
76

77
        while que1 or que2:
78
            while que1:
79
                k2, mi2, ci2 = que1.popleft()
80
                t = dp[k2][mi2][ci2]
81
                k = 1 - k2
82
                i = [mi2, ci2]
83
                for x, y in adj_grid(*i2xy(i[k]), jps[k]):
84
                    i[k] = xy2i(x, y)
85
                    if dp[k][i[0]][i[1]] is None:
86
                        dp[k][i[0]][i[1]] = t  # directly determine the value
87
                        if (k, i[0], i[1]) == (0, mi, ci):
88
                            return t
89
                        que2.append((k, i[0], i[1]))
90
            while que2:
91
                k2, mi2, ci2 = que2.popleft()
92
                t = dp[k2][mi2][ci2]
93
                k = 1 - k2
94
                i = [mi2, ci2]
95
                for x, y in adj_grid(*i2xy(i[k]), jps[k]):
96
                    i[k] = xy2i(x, y)
97
                    if dp[k][i[0]][i[1]] is None:
98
                        adj[k][i[0]][i[1]] -= 1  # only change the counter
99
                        if adj[k][i[0]][i[1]] == 0:
100
                            dp[k][i[0]][i[1]] = t
101
                            if (k, i[0], i[1]) == (0, mi, ci):
102
                                return t
103
                            que1.append((k, i[0], i[1]))
104

105
        return dp[0][mi][ci]