Skip to content

576. Out of Boundary Paths 👍

Approach 1: Top-down

  • Time: $O(mnN)$
  • Space: $O(mnN)$
 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
class Solution {
 public:
  int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
    this->m = m;
    this->n = n;
    // dp[k][i][j] := # of paths to move the ball (i, j) out of bound w/ k moves
    dp.resize(maxMove + 1, vector<vector<int>>(m, vector<int>(n, -1)));
    return findPaths(maxMove, startRow, startColumn);
  }

 private:
  static constexpr int kMod = 1'000'000'007;
  int m;
  int n;
  vector<vector<vector<int>>> dp;

  int findPaths(int k, int i, int j) {
    if (i < 0 || i == m || j < 0 || j == n)
      return 1;
    if (k == 0)
      return 0;
    if (dp[k][i][j] != -1)
      return dp[k][i][j];
    return dp[k][i][j] =
               ((findPaths(k - 1, i + 1, j) + findPaths(k - 1, i - 1, j)) %
                    kMod +
                (findPaths(k - 1, i, j + 1) + findPaths(k - 1, i, j - 1)) %
                    kMod) %
               kMod;
  }
};

 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
class Solution {
  public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
    this.m = m;
    this.n = n;
    // dp[k][i][j] := # of paths to move the ball (i, j) out of bound w/ k moves
    dp = new Integer[maxMove + 1][m][n];
    return findPaths(maxMove, startRow, startColumn);
  }

  private static final int kMod = 1_000_000_007;
  private int m;
  private int n;
  private Integer[][][] dp;

  private int findPaths(int k, int i, int j) {
    if (i < 0 || i == m || j < 0 || j == n)
      return 1;
    if (k == 0)
      return 0;
    if (dp[k][i][j] != null)
      return dp[k][i][j];
    return dp[k][i][j] = ((findPaths(k - 1, i + 1, j) + findPaths(k - 1, i - 1, j)) % kMod +
                          (findPaths(k - 1, i, j + 1) + findPaths(k - 1, i, j - 1)) % kMod) %
                         kMod;
  }
}

Approach 2: Bottom-up

  • Time: $O(mnN)$
  • Space: $O(mn)$
 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
class Solution {
 public:
  int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
    constexpr int kMod = 1'000'000'007;
    const vector<int> dirs{0, 1, 0, -1, 0};
    int ans = 0;
    // dp[i][j] := # of paths to move the ball (i, j) out of bound
    vector<vector<int>> dp(m, vector<int>(n));
    dp[startRow][startColumn] = 1;

    while (maxMove--) {
      vector<vector<int>> newDp(m, vector<int>(n));
      for (int r = 0; r < m; ++r)
        for (int c = 0; c < n; ++c)
          if (dp[r][c] > 0)
            for (int k = 0; k < 4; ++k) {
              const int x = r + dirs[k];
              const int y = c + dirs[k + 1];
              if (x < 0 || x == m || y < 0 || y == n)
                ans = (ans + dp[r][c]) % kMod;
              else
                newDp[x][y] = (newDp[x][y] + dp[r][c]) % kMod;
            }
      dp = move(newDp);
    }

    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
class Solution {
  public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
    final int kMod = 1_000_000_007;
    final int[] dirs = {0, 1, 0, -1, 0};
    int ans = 0;
    // dp[i][j] := # of paths to move the ball (i, j) out of bound
    int[][] dp = new int[m][n];
    dp[startRow][startColumn] = 1;

    while (maxMove-- > 0) {
      int[][] newDp = new int[m][n];
      for (int r = 0; r < m; ++r)
        for (int c = 0; c < n; ++c)
          if (dp[r][c] > 0)
            for (int k = 0; k < 4; ++k) {
              final int x = r + dirs[k];
              final int y = c + dirs[k + 1];
              if (x < 0 || x == m || y < 0 || y == n)
                ans = (ans + dp[r][c]) % kMod;
              else
                newDp[x][y] = (newDp[x][y] + dp[r][c]) % kMod;
            }
      dp = newDp;
    }

    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
class Solution:
  def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
    kMod = 1_000_000_007
    dirs = [1, 0, -1, 0, 1]
    ans = 0
    # dp[i][j] := # of paths to move the ball (i, j) out of bound
    dp = [[0] * n for _ in range(m)]
    dp[startRow][startColumn] = 1

    for _ in range(maxMove):
      newDp = [[0] * n for _ in range(m)]
      for r in range(m):
        for c in range(n):
          if dp[r][c] > 0:
            for dx, dy in zip(dirs, dirs[1:]):
              x = r + dx
              y = c + dy
              if x < 0 or x == m or y < 0 or y == n:
                ans = (ans + dp[r][c]) % kMod
              else:
                newDp[x][y] = (newDp[x][y] + dp[r][c]) % kMod
      dp = newDp

    return ans