2912：在网格上移动到目的地的方法数（★★）

2023-10-23 约 684 字预计阅读 2 分钟次阅读

力扣第 2912 题

题目

给定两个整数 n 和 m，它们表示一个 下标从 1 开始 的网格的大小。还给定一个整数 k，以及两个 下标从 1 开始 的整数数组 source 和 dest。这两个数组 source 和 dest 形如 [x, y]，表示网格上的一个单元格。

你可以按照以下方式在网格上移动：

你可以从单元格 [x1, y1] 移动到 [x2, y2]，只要 x1 == x2 或 y1 == y2。
注意，你不能移动到当前所在的单元格，即 x1 == x2 且 y1 == y2。

请返回你在网格上从 source 到 dest 移动 k 次一共可以有 多少种 方法。

由于答案可能非常大，因此请对 10⁹ + 7 取模后返回。

示例 1:

输入： n = 3, m = 2, k = 2, source = [1,1], dest = [2,2]
输出： 2
解释： 有两种可能的方式从 [1,1] 到达 [2,2]：
- [1,1] -> [1,2] -> [2,2]
- [1,1] -> [2,1] -> [2,2]

示例 2:

输入： n = 3, m = 4, k = 3, source = [1,2], dest = [2,3]
输出： 9
解释： 有 9 种可能的方式从 [1,2] 到达 [2,3]：:
- [1,2] -> [1,1] -> [1,3] -> [2,3]
- [1,2] -> [1,1] -> [2,1] -> [2,3]
- [1,2] -> [1,3] -> [3,3] -> [2,3]
- [1,2] -> [1,4] -> [1,3] -> [2,3]
- [1,2] -> [1,4] -> [2,4] -> [2,3]
- [1,2] -> [2,2] -> [2,1] -> [2,3]
- [1,2] -> [2,2] -> [2,4] -> [2,3]
- [1,2] -> [3,2] -> [2,2] -> [2,3]
- [1,2] -> [3,2] -> [3,3] -> [2,3]

提示：

2 <= n, m <= 10⁹
1 <= k <= 10⁵
source.length == dest.length == 2
1 <= source[1], dest[1] <= n
1 <= source[2], dest[2] <= m

分析

#1 dp

移动中，实际上只关心跟目标单元格的横纵坐标是否相等
因此，维护 4 个状态表示与目标的横纵坐标相等情况，递推即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def numberOfWays(self, n: int, m: int, k: int, source: List[int], dest: List[int]) -> int:
        mod = 10**9+7
        sx,sy = source
        tx,ty = dest
        f = [0]*4
        f[(sx==tx)+2*(sy==ty)] = 1
        for _ in range(k):
            g = [0]*4
            g[0] = f[0]*(n+m-4)+f[1]*(n-1)+f[2]*(m-1)
            g[1] = f[0]+f[1]*(m-2)+f[3]*(m-1)
            g[2] = f[0]+f[2]*(n-2)+f[3]*(n-1)
            g[3] = f[1]+f[2]
            f = [x%mod for x in g]
        return f[-1]

1057 ms

#2 矩阵快速幂

每轮的递推系数相同，可以用矩阵快速幂优化

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


mod = 10**9+7
def mul(A,B):
    return [[sum(a*b for a,b in zip(r,c))%mod for c in zip(*B)] for r in A]
def mpow(mat,n):
    res = mat
    for i in range(n.bit_length()-2,-1,-1):
        res = mul(res,res)
        if n>>i&1:
            res = mul(res,mat)
    return res

class Solution:
    def numberOfWays(self, n: int, m: int, k: int, source: List[int], dest: List[int]) -> int:
        sx,sy = source
        tx,ty = dest
        f = [[0] for _ in range(4)]
        f[(sx==tx)+2*(sy==ty)][0] = 1
        g = [[n+m-4,n-1,m-1,0],[1,m-2,0,m-1],[1,0,n-2,n-1],[0,1,1,0]]
        res = mul(mpow(g,k),f)
        return res[-1][-1]

437 ms

目录

2912：在网格上移动到目的地的方法数（★★）

题目

分析

#1 dp

#2 矩阵快速幂

解答