2912. Number of Ways to Reach Destination in the Grid 🔒

Description

You are given two integers n and m which represent the size of a 1-indexed grid. You are also given an integer k, a 1-indexed integer array source and a 1-indexed integer array dest, where source and dest are in the form [x, y] representing a cell on the given grid.

You can move through the grid in the following way:

You can go from cell [x₁, y₁] to cell [x₂, y₂] if either x₁ == x₂ or y₁ == y₂.
Note that you can't move to the cell you are already in e.g. x₁ == x₂ and y₁ == y₂.

Return the number of ways you can reach dest from source by moving through the grid exactly k times.

Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

Input: n = 3, m = 2, k = 2, source = [1,1], dest = [2,2]
Output: 2
Explanation: There are 2 possible sequences of reaching [2,2] from [1,1]:
- [1,1] -> [1,2] -> [2,2]
- [1,1] -> [2,1] -> [2,2]

Example 2:

Input: n = 3, m = 4, k = 3, source = [1,2], dest = [2,3]
Output: 9
Explanation: There are 9 possible sequences of reaching [2,3] from [1,2]:
- [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]

Constraints:

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

Solutions

Solution 1: Dynamic Programming

Thinking

Each step changes the row or the column, and we want to sit at \(dest\) after \(k\) steps. The grid can be \(10^9\) on a side, so per-cell states are impossible. Relative to \(source\) there are only four kinds of cells: itself, same column, same row, or neither.

A four-vector \(f\) stores the number of ways to each kind; one step mixes only these four kinds, with coefficients from \(n\) and \(m\). After \(k\) iterations, pick the component that matches how \(dest\) sits relative to \(source\).

We define the following states:

\(f[0]\) represents the number of ways to move from source to source itself;
\(f[1]\) represents the number of ways to move from source to another row in the same column;
\(f[2]\) represents the number of ways to move from source to another column in the same row;
\(f[3]\) represents the number of ways to move from source to another row and another column.

Initially, \(f[0] = 1\), and the other states are all \(0\).

For each state, we can calculate the current state based on the previous state, as follows:

\[ \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} \]

We loop \(k\) times, and finally check whether source and dest are in the same row or column, and return the corresponding state.

The time complexity is \(O(k)\), where \(k\) is the number of moves. The space complexity is \(O(1)\).

Python3JavaC++Go

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]

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];
    }
}

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];
    }
};

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]
}

2912. Number of Ways to Reach Destination in the Grid 🔒

Description

Solutions

Solution 1: Dynamic Programming

Comments