Skip to content

2912. Number of Ways to Reach Destination in the Grid

Approach 1: 2D DP

  • Time: $O(k)$
  • Space: $O(k)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
 public:
  int numberOfWays(int n, int m, int k, vector<int>& source,
                   vector<int>& dest) {
    constexpr int kMod = 1'000'000'007;
    // dp[i][0] := the the number of ways of `source` to `dest` using i
    // steps dp[i][1] := the the number of ways of `source` to dest's row
    // using i steps dp[i][2] := the the number of ways of `source` to
    // dest's col using i steps dp[i][3] := the the number of ways of
    // `source` to others using i steps
    vector<vector<int>> dp(k + 1, vector<int>(4));
    if (source == dest)
      dp[0][0] = 1;
    else if (source[0] == dest[0])
      dp[0][1] = 1;
    else if (source[1] == dest[1])
      dp[0][2] = 1;
    else
      dp[0][3] = 1;

    for (int i = 1; i <= k; i++) {
      dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % kMod;
      dp[i][1] = ((dp[i - 1][0] * (m - 1L) +  // -self
                   dp[i - 1][1] * (m - 2L) +  // -self, -center
                   dp[i - 1][3]) %
                  kMod);
      dp[i][2] = ((dp[i - 1][0] * (n - 1L) +  // -self
                   dp[i - 1][2] * (n - 2L) +  // -self, -center
                   dp[i - 1][3]) %
                  kMod);
      dp[i][3] = ((dp[i - 1][1] * (n - 1L) +         // -self
                   dp[i - 1][2] * (m - 1L) +         // -self
                   dp[i - 1][3] * (m + n - 1 - 3L))  // -self, -row, -col
                  % kMod);
    }

    return dp[k][0];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
  public int numberOfWays(int n, int m, int k, int[] source, int[] dest) {
    final int MOD = 1_000_000_007;
    // dp[i][0] := the the number of ways of `source` to `dest` using i steps
    // dp[i][1] := the the number of ways of `source` to dest's row using i steps
    // dp[i][2] := the the number of ways of `source` to dest's col using i steps
    // dp[i][3] := the the number of ways of `source` to others using i steps
    int[][] dp = new int[k + 1][4];
    if (Arrays.equals(source, dest))
      dp[0][0] = 1;
    else if (source[0] == dest[0])
      dp[0][1] = 1;
    else if (source[1] == dest[1])
      dp[0][2] = 1;
    else
      dp[0][3] = 1;

    for (int i = 1; i <= k; i++) {
      dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % MOD;
      dp[i][1] = (int) ((dp[i - 1][0] * (m - 1L) + // -self
                         dp[i - 1][1] * (m - 2L) + // -self, -center
                         dp[i - 1][3]) %
                        MOD);
      dp[i][2] = (int) ((dp[i - 1][0] * (n - 1L) + // -self
                         dp[i - 1][2] * (n - 2L) + // -self, -center
                         dp[i - 1][3]) %
                        MOD);
      dp[i][3] = (int) ((dp[i - 1][1] * (n - 1L) +        // -self
                         dp[i - 1][2] * (m - 1L) +        // -self
                         dp[i - 1][3] * (m + n - 1 - 3L)) // -self, -row, -col
                        % MOD);
    }

    return dp[k][0];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
  def numberOfWays(
      self,
      n: int,
      m: int,
      k: int,
      source: list[int],
      dest: list[int],
  ) -> int:
    MOD = 1_000_000_007
    # dp[i][0] := the the number of ways of `source` to `dest` using i steps
    # dp[i][1] := the the number of ways of `source` to dest's row using i steps
    # dp[i][2] := the the number of ways of `source` to dest's col using i steps
    # dp[i][3] := the the number of ways of `source` to others using i steps
    dp = [[0] * 4 for _ in range(k + 1)]
    if source == dest:
      dp[0][0] = 1
    elif source[0] == dest[0]:
      dp[0][1] = 1
    elif source[1] == dest[1]:
      dp[0][2] = 1
    else:
      dp[0][3] = 1

    for i in range(1, k + 1):
      dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % MOD
      dp[i][1] = (dp[i - 1][0] * (m - 1) +  # -self
                  dp[i - 1][1] * (m - 2) +  # -self, -center
                  dp[i - 1][3]) % MOD
      dp[i][2] = (dp[i - 1][0] * (n - 1) +  # -self
                  dp[i - 1][2] * (n - 2) +  # -self, -center
                  dp[i - 1][3]) % MOD
      dp[i][3] = (dp[i - 1][1] * (n - 1) +  # -self
                  dp[i - 1][2] * (m - 1) +  # -self
                  dp[i - 1][3] * (m + n - 1 - 3)) % MOD  # -self, -row, -col

    return dp[k][0]

Approach 2: 1D DP

  • Time: $O(k)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
 public:
  int numberOfWays(int n, int m, int k, vector<int>& source,
                   vector<int>& dest) {
    constexpr int kMod = 1'000'000'007;
    // the number of ways of `source` to `dest` using steps so far
    int ans = source[0] == dest[0] && source[1] == dest[1];
    // the number of ways of `source` to dest's row using steps so far
    int row = source[0] == dest[0] && source[1] != dest[1];
    // the number of ways of `source` to dest's col using steps so far
    int col = source[0] != dest[0] && source[1] == dest[1];
    // the number of ways of `source` to others using steps so far
    int others = source[0] != dest[0] && source[1] != dest[1];

    for (int i = 0; i < k; ++i) {
      const int nextAns = (row + col) % kMod;
      const int nextRow = static_cast<int>((ans * (m - 1L) +  // -self
                                            row * (m - 2L) +  //-self, -center
                                            others) %
                                           kMod);
      const int nextCol = static_cast<int>((ans * (n - 1L) +  // -self
                                            col * (n - 2L) +  // -self, -center
                                            others) %
                                           kMod);
      const int nextOthers =
          static_cast<int>((row * (n - 1L) +              // -self
                            col * (m - 1L) +              // -self
                            others * (m + n - 1 - 3L)) %  // -self, -row, -col
                           kMod);
      ans = nextAns;
      row = nextRow;
      col = nextCol;
      others = nextOthers;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
  public int numberOfWays(int n, int m, int k, int[] source, int[] dest) {
    final int MOD = 1_000_000_007;
    // the number of ways of `source` to `dest` using steps so far
    int ans = (source[0] == dest[0] && source[1] == dest[1]) ? 1 : 0;
    // the number of ways of `source` to dest's row using steps so far
    int row = (source[0] == dest[0] && source[1] != dest[1]) ? 1 : 0;
    // the number of ways of `source` to dest's col using steps so far
    int col = (source[0] != dest[0] && source[1] == dest[1]) ? 1 : 0;
    // the number of ways of `source` to others using steps so far
    int others = (source[0] != dest[0] && source[1] != dest[1]) ? 1 : 0;

    for (int i = 0; i < k; ++i) {
      final int nextAns = (row + col) % MOD;
      final int nextRow = (int) ((ans * (m - 1L) + // -self
                                  row * (m - 2L) + //-self, -center
                                  others) %
                                 MOD);
      final int nextCol = (int) ((ans * (n - 1L) + // -self
                                  col * (n - 2L) + // -self, -center
                                  others) %
                                 MOD);
      final int nextOthers = (int) ((row * (n - 1L) +             // -self
                                     col * (m - 1L) +             // -self
                                     others * (m + n - 1 - 3L)) % // -self, -row, -col
                                    MOD);
      ans = nextAns;
      row = nextRow;
      col = nextCol;
      others = nextOthers;
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:
  def numberOfWays(
      self,
      n: int,
      m: int,
      k: int,
      source: list[int],
      dest: list[int],
  ) -> int:
    MOD = 1_000_000_007
    # the number of ways of `source` to `dest` using steps so far
    ans = int(source == dest)
    # the number of ways of `source` to dest's row using steps so far
    row = int(source[0] == dest[0] and source[1] != dest[1])
    # the number of ways of `source` to dest's col using steps so far
    col = int(source[0] != dest[0] and source[1] == dest[1])
    # the number of ways of `source` to others using steps so far
    others = int(source[0] != dest[0] and source[1] != dest[1])

    for _ in range(k):
      nextAns = (row + col) % MOD
      nextRow = (ans * (m - 1) +  # -self
                 row * (m - 2) +  # -self, -center
                 others) % MOD
      nextCol = (ans * (n - 1) +  # -self
                 col * (n - 2) +  # -self, -center
                 others) % MOD
      nextOthers = (row * (n - 1) +  # -self
                    col * (m - 1) +  # -self
                    others * (m + n - 1 - 3)) % MOD  # -self, -row, -col
      ans = nextAns
      row = nextRow
      col = nextCol
      others = nextOthers

    return ans