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 eitherx1 == x2
ory1 == y2
. - Note that you can't move to the cell you are already in e.g.
x1 == x2
andy1 == 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
tosource
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)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|