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 [x1, y1] to cell [x2, y2] if either x1 == x2 or y1 == y2.
• Note that you can't move to the cell you are already in e.g. x1 == x2 and y1 == y2.

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 109 + 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 <= 109
• 1 <= k <= 105
• source.length == dest.length == 2
• 1 <= source[1], dest[1] <= n
• 1 <= source[2], dest[2] <= m

Solutions

Solution 1: Dynamic Programming

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)\).

Python3Python3JavaC++Go

class Solution:
    def numberOfWays(
        self, n: int, m: int, k: int, source: List[int], dest: List[int]
    ) -> int:
        mod = 10**9 + 7
        a, b, c, d = 1, 0, 0, 0
        for _ in range(k):
            aa = ((n - 1) * b + (m - 1) * c) % mod
            bb = (a + (n - 2) * b + (m - 1) * d) % mod
            cc = (a + (m - 2) * c + (n - 1) * d) % mod
            dd = (b + c + (n - 2) * d + (m - 2) * d) % mod
            a, b, c, d = aa, bb, cc, dd
        if source[0] == dest[0]:
            return a if source[1] == dest[1] else c
        return b if source[1] == dest[1] else d

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

Comments