跳转至

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 次一共可以有 多少种 方法。

由于答案可能非常大，因此请对 109 + 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 <= 109
  • 1 <= k <= 105
  • source.length == dest.length == 2
  • 1 <= source[1], dest[1] <= n
  • 1 <= source[2], dest[2] <= m

解法

方法一：动态规划

思考

每一步只能改行或改列，\(k\) 步后到达 \(dest\)。网格可达 \(10^9\) 量级，不能按格子建状态。相对 \(source\) 仅有四类位置：自身、同列不同行、同行不同列、行列皆不同。

用四维向量 \(f\) 记录这四类格子的方案数，一步转移只在这四类之间发生，系数由 \(n,m\) 决定。迭代 \(k\) 次后，按 \(dest\) 与 \(source\) 的行列关系选取对应分量。

我们定义以下几个状态，其中：

  • \(f[0]\) 表示从 \(source\) 到 \(source\) 本身的方法数；
  • \(f[1]\) 表示从 \(source\) 移动到同一列其它行的方法数；
  • \(f[2]\) 表示从 \(source\) 移动到同一行其它列的方法数；
  • \(f[3]\) 表示从 \(source\) 移动到其它行其它列的方法数。

初始时，\(f[0] = 1\)，其余状态均为 \(0\)。

对于每个状态，我们可以根据上一次的状态计算出当前的状态，具体如下：

\[ \begin{aligned} g[0] &= (n - 1) \times f[1] + (m - 1) \times f[2] \\ g[1] &= f[0] + (n - 2) \times f[1] + (m - 1) \times f[3] \\ g[2] &= f[0] + (m - 2) \times f[2] + (n - 1) \times f[3] \\ g[3] &= f[1] + f[2] + (n - 2) \times f[3] + (m - 2) \times f[3] \end{aligned} \]

我们循环 \(k\) 次，最后判断 \(source\) 和 \(dest\) 是否在同一行或同一列，返回对应的状态即可。

时间复杂度 \(O(k)\)，其中 \(k\) 为移动次数。空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def numberOfWays(
        self, n: int, m: int, k: int, source: List[int], dest: List[int]
    ) -> int:
        mod = 10**9 + 7
        f = [1, 0, 0, 0]
        for _ in range(k):
            g = [0] * 4
            g[0] = ((n - 1) * f[1] + (m - 1) * f[2]) % mod
            g[1] = (f[0] + (n - 2) * f[1] + (m - 1) * f[3]) % mod
            g[2] = (f[0] + (m - 2) * f[2] + (n - 1) * f[3]) % mod
            g[3] = (f[1] + f[2] + (n - 2) * f[3] + (m - 2) * f[3]) % mod
            f = g
        if source[0] == dest[0]:
            return f[0] if source[1] == dest[1] else f[2]
        return f[1] if source[1] == dest[1] else f[3]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int numberOfWays(int n, int m, int k, int[] source, int[] dest) {
        final int mod = 1000000007;
        long[] f = new long[4];
        f[0] = 1;
        while (k-- > 0) {
            long[] g = new long[4];
            g[0] = ((n - 1) * f[1] + (m - 1) * f[2]) % mod;
            g[1] = (f[0] + (n - 2) * f[1] + (m - 1) * f[3]) % mod;
            g[2] = (f[0] + (m - 2) * f[2] + (n - 1) * f[3]) % mod;
            g[3] = (f[1] + f[2] + (n - 2) * f[3] + (m - 2) * f[3]) % mod;
            f = g;
        }
        if (source[0] == dest[0]) {
            return source[1] == dest[1] ? (int) f[0] : (int) f[2];
        }
        return source[1] == dest[1] ? (int) f[1] : (int) f[3];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int numberOfWays(int n, int m, int k, vector<int>& source, vector<int>& dest) {
        const int mod = 1e9 + 7;
        vector<long long> f(4);
        f[0] = 1;
        while (k--) {
            vector<long long> g(4);
            g[0] = ((n - 1) * f[1] + (m - 1) * f[2]) % mod;
            g[1] = (f[0] + (n - 2) * f[1] + (m - 1) * f[3]) % mod;
            g[2] = (f[0] + (m - 2) * f[2] + (n - 1) * f[3]) % mod;
            g[3] = (f[1] + f[2] + (n - 2) * f[3] + (m - 2) * f[3]) % mod;
            f = move(g);
        }
        if (source[0] == dest[0]) {
            return source[1] == dest[1] ? f[0] : f[2];
        }
        return source[1] == dest[1] ? f[1] : f[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
func numberOfWays(n int, m int, k int, source []int, dest []int) int {
    const mod int = 1e9 + 7
    f := []int{1, 0, 0, 0}
    for i := 0; i < k; i++ {
        g := make([]int, 4)
        g[0] = ((n-1)*f[1] + (m-1)*f[2]) % mod
        g[1] = (f[0] + (n-2)*f[1] + (m-1)*f[3]) % mod
        g[2] = (f[0] + (m-2)*f[2] + (n-1)*f[3]) % mod
        g[3] = (f[1] + f[2] + (n-2)*f[3] + (m-2)*f[3]) % mod
        f = g
    }

    if source[0] == dest[0] {
        if source[1] == dest[1] {
            return f[0]
        }
        return f[2]
    }

    if source[1] == dest[1] {
        return f[1]
    }
    return f[3]
}

评论