Problem

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.

Examples

Example 1:

1
2
3
4
5

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:

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

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^9
  • 1 <= k <= 10^5
  • source.length == dest.length == 2
  • 1 <= source[1], dest[1] <= n
  • 1 <= source[2], dest[2] <= m

Solution

Method 1 – Dynamic Programming with State Compression

Intuition

Since the grid is huge, we can’t use a 2D DP. The only thing that matters is whether we are in the same row or same column as the destination. We can use a 2-state DP: at each step, track the number of ways to be in the same row as dest, and the number of ways to be in the same column as dest.

Approach

  1. Let dp_row = number of ways to be in the same row as dest after t steps, dp_col = number of ways to be in the same column as dest after t steps.
  2. At each step, you can move from row to col or col to row, except you can’t stay in the same cell.
  3. Use matrix exponentiation or iterative DP for k steps, updating dp_row and dp_col at each step.
  4. Initialize dp_row and dp_col based on whether source is in the same row or column as dest.
  5. Return the number of ways to reach dest in exactly k steps.

Code

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

class Solution {
public:
    int numberOfWays(int n, int m, int k, vector<int>& source, vector<int>& dest) {
        const int mod = 1e9+7;
        int sr = source[0], sc = source[1], dr = dest[0], dc = dest[1];
        vector<long long> dp(2);
        dp[0] = (sr == dr); // same row
        dp[1] = (sc == dc); // same col
        for (int step = 0; step < k; ++step) {
            vector<long long> ndp(2);
            ndp[0] = ((dp[1] * (n-1)) % mod);
            ndp[1] = ((dp[0] * (m-1)) % mod);
            dp = ndp;
        }
        return (int)dp[0];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func numberOfWays(n, m, k int, source, dest []int) int {
    mod := int(1e9+7)
    sr, sc, dr, dc := source[0], source[1], dest[0], dest[1]
    dp := [2]int64{}
    if sr == dr { dp[0] = 1 }
    if sc == dc { dp[1] = 1 }
    for step := 0; step < k; step++ {
        ndp := [2]int64{}
        ndp[0] = (dp[1] * int64(n-1)) % int64(mod)
        ndp[1] = (dp[0] * int64(m-1)) % int64(mod)
        dp = ndp
    }
    return int(dp[0])
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int numberOfWays(int n, int m, int k, int[] source, int[] dest) {
        int mod = 1_000_000_007;
        int sr = source[0], sc = source[1], dr = dest[0], dc = dest[1];
        long[] dp = new long[2];
        dp[0] = (sr == dr) ? 1 : 0;
        dp[1] = (sc == dc) ? 1 : 0;
        for (int step = 0; step < k; step++) {
            long[] ndp = new long[2];
            ndp[0] = (dp[1] * (n-1)) % mod;
            ndp[1] = (dp[0] * (m-1)) % mod;
            dp = ndp;
        }
        return (int)dp[0];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun numberOfWays(n: Int, m: Int, k: Int, source: IntArray, dest: IntArray): Int {
        val mod = 1_000_000_007
        val sr = source[0]; val sc = source[1]; val dr = dest[0]; val dc = dest[1]
        var dp = longArrayOf(if (sr == dr) 1L else 0L, if (sc == dc) 1L else 0L)
        repeat(k) {
            val ndp = longArrayOf((dp[1] * (n-1)) % mod, (dp[0] * (m-1)) % mod)
            dp = ndp
        }
        return dp[0].toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def numberOfWays(self, n: int, m: int, k: int, source: list[int], dest: list[int]) -> int:
        mod = 10**9+7
        sr, sc, dr, dc = source[0], source[1], dest[0], dest[1]
        dp = [int(sr == dr), int(sc == dc)]
        for _ in range(k):
            ndp = [0, 0]
            ndp[0] = dp[1] * (n-1) % mod
            ndp[1] = dp[0] * (m-1) % mod
            dp = ndp
        return dp[0]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn number_of_ways(n: i32, m: i32, k: i32, source: Vec<i32>, dest: Vec<i32>) -> i32 {
        let (sr, sc, dr, dc) = (source[0], source[1], dest[0], dest[1]);
        let mut dp = [if sr == dr { 1 } else { 0 }, if sc == dc { 1 } else { 0 }];
        let modulo = 1_000_000_007;
        for _ in 0..k {
            let ndp0 = (dp[1] as i64 * (n-1) as i64 % modulo) as i32;
            let ndp1 = (dp[0] as i64 * (m-1) as i64 % modulo) as i32;
            dp = [ndp0, ndp1];
        }
        dp[0]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    numberOfWays(n: number, m: number, k: number, source: number[], dest: number[]): number {
        const mod = 1_000_000_007
        const [sr, sc, dr, dc] = source.concat(dest)
        let dp = [sr === dr ? 1 : 0, sc === dc ? 1 : 0]
        for (let step = 0; step < k; step++) {
            const ndp = [dp[1] * (n-1) % mod, dp[0] * (m-1) % mod]
            dp = ndp
        }
        return dp[0]
    }
}

Complexity

  • ⏰ Time complexity: O(k), where k is the number of steps.
  • 🧺 Space complexity: O(1), only a few variables are used.