1728：猫和老鼠 II（2849 分）

Ian

2021-01-17 约 1192 字预计阅读 3 分钟次阅读

力扣第 224 场周赛第 4 题

题目

一只猫和一只老鼠在玩一个叫做猫和老鼠的游戏。

它们所处的环境设定是一个 rows x cols 的方格 grid ，其中每个格子可能是一堵墙、一块地板、一位玩家（猫或者老鼠）或者食物。

玩家由字符 'C' （代表猫）和 'M' （代表老鼠）表示。
地板由字符 '.' 表示，玩家可以通过这个格子。
墙用字符 '#' 表示，玩家不能通过这个格子。
食物用字符 'F' 表示，玩家可以通过这个格子。
字符 'C' ， 'M' 和 'F' 在 grid 中都只会出现一次。

猫和老鼠按照如下规则移动：

老鼠 先移动 ，然后两名玩家轮流移动。
每一次操作时，猫和老鼠可以跳到上下左右四个方向之一的格子，他们不能跳过墙也不能跳出 grid 。
catJump 和 mouseJump 是猫和老鼠分别跳一次能到达的最远距离，它们也可以跳小于最大距离的长度。
它们可以停留在原地。
老鼠可以跳跃过猫的位置。

游戏有 4 种方式会结束：

如果猫跟老鼠处在相同的位置，那么猫获胜。
如果猫先到达食物，那么猫获胜。
如果老鼠先到达食物，那么老鼠获胜。
如果老鼠不能在 1000 次操作以内到达食物，那么猫获胜。

给你 rows x cols 的矩阵 grid 和两个整数 catJump 和 mouseJump ，双方都采取最优策略，如果老鼠获胜，那么请你返回 true ，否则返回 false 。

示例 1：

输入：grid = ["####F","#C...","M...."], catJump = 1, mouseJump = 2
输出：true
解释：猫无法抓到老鼠，也没法比老鼠先到达食物。

示例 2：

输入：grid = ["M.C...F"], catJump = 1, mouseJump = 4
输出：true

示例 3：

输入：grid = ["M.C...F"], catJump = 1, mouseJump = 3
输出：false

示例 4：

输入：grid = ["C...#","...#F","....#","M...."], catJump = 2, mouseJump = 5
输出：false

示例 5：

输入：grid = [".M...","..#..","#..#.","C#.#.","...#F"], catJump = 3, mouseJump = 1
输出：true

提示：

rows == grid.length
cols = grid[i].length
1 <= rows, cols <= 8
grid[i][j] 只包含字符 'C' ，'M' ，'F' ，'.' 和 '#' 。
grid 中只包含一个 'C' ，'M' 和 'F' 。
1 <= catJump, mouseJump <= 8

相似问题：

分析

#1

0913 进阶版，只是建图更麻烦点
直觉上来说，老鼠如果能到达食物，必然少于 1000 次操作，可以忽略这个条件

 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


class Solution:
    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:
        @cache
        def gen(i,jump):
            res = set()
            x,y = divmod(i,n)
            if grid[x][y] != '#':
                for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
                    for k in range(jump+1):
                        x2,y2 = x+k*dx,y+k*dy
                        if 0<=x2<m and 0<=y2<n:
                            if grid[x2][y2]=='#':
                                break
                            res.add(x2*n+y2)
            return res
        m,n = len(grid), len(grid[0])
        d = {grid[i][j]:(i,j) for i in range(m) for j in range(n)}
        C,M,F = [d[c][0]*n+d[c][1] for c in 'CMF']
        g,deg = defaultdict(list), defaultdict(int)
        for i,j in product(range(m*n),range(m*n)):
            for k in gen(i,mouseJump):
                g[(k,j,2)].append((i,j,1))
                deg[(i,j,1)] += 1
            for k in gen(j,catJump):
                g[(i,k,1)].append((i,j,2))
                deg[(i,j,2)] += 1
        f = {}
        for i in range(m*n):
            f[(F,i,1)] = f[(F,i,2)] = 1
            f[(i,i,1)] = f[(i,i,2)] = 2
            f[(i,F,1)] = f[(i,F,2)] = 2
        Q = deque(f)                  
        while Q:
            u = Q.popleft()
            if u==(M,C,1):                
                return f[u]==1
            for v in g[u]:
                if v in f:
                    continue
                if v[-1]==f[u]:
                    f[v] = f[u]
                    Q.append(v)
                else:
                    deg[v]-=1
                    if deg[v]==0:
                        f[v] = f[u]
                        Q.append(v)
        return False

640 ms

#2

保险起见，也可以在拓扑排序时，维护操作次数

解答

 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


class Solution:
    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:
        @cache
        def gen(i,jump):
            res = set()
            x,y = divmod(i,n)
            if grid[x][y] != '#':
                for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
                    for k in range(jump+1):
                        x2,y2 = x+k*dx,y+k*dy
                        if 0<=x2<m and 0<=y2<n:
                            if grid[x2][y2]=='#':
                                break
                            res.add(x2*n+y2)
            return res
        m,n = len(grid), len(grid[0])
        d = {grid[i][j]:(i,j) for i in range(m) for j in range(n)}
        C,M,F = [d[c][0]*n+d[c][1] for c in 'CMF']
        g,deg = defaultdict(list), defaultdict(int)
        for i,j in product(range(m*n),range(m*n)):
            for k in gen(i,mouseJump):
                g[(k,j,2)].append((i,j,1))
                deg[(i,j,1)] += 1
            for k in gen(j,catJump):
                g[(i,k,1)].append((i,j,2))
                deg[(i,j,2)] += 1
        f = {}
        for i in range(m*n):
            f[(F,i,1)] = f[(F,i,2)] = 1
            f[(i,i,1)] = f[(i,i,2)] = 2
            f[(i,F,1)] = f[(i,F,2)] = 2
        Q = deque([(u,0) for u in f])                  
        while Q:
            u,w = Q.popleft()
            if u==(M,C,1):                
                return f[u]==1
            if w==1000:
                return False
            for v in g[u]:
                if v in f:
                    continue
                if v[-1]==f[u]:
                    f[v] = f[u]
                    Q.append((v,w+1))
                else:
                    deg[v]-=1
                    if deg[v]==0:
                        f[v] = f[u]
                        Q.append((v,w+1))
        return False

671 ms

目录

1728：猫和老鼠 II（2849 分）

题目

分析

#1

#2

解答