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
class Solution {
 public:
  int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
    vector<vector<vector<int>>> mem(maxMove + 1,
                                    vector<vector<int>>(m, vector<int>(n, -1)));
    return findPaths(m, n, maxMove, startRow, startColumn, mem);
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  // Returns the number of paths to move the ball at (i, j) out-of-bounds with k
  // moves.
  int findPaths(int m, int n, int k, int i, int j,
                vector<vector<vector<int>>>& mem) {
    if (i < 0 || i == m || j < 0 || j == n)
      return 1;
    if (k == 0)
      return 0;
    if (mem[k][i][j] != -1)
      return mem[k][i][j];
    return mem[k][i][j] = (findPaths(m, n, k - 1, i + 1, j, mem) * 1L +
                           findPaths(m, n, k - 1, i - 1, j, mem) +
                           findPaths(m, n, k - 1, i, j + 1, mem) +
                           findPaths(m, n, k - 1, i, j - 1, mem)) %
                          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
class Solution {
  public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
    Integer[][][] mem = new Integer[maxMove + 1][m][n];
    return findPaths(m, n, maxMove, startRow, startColumn, mem);
  }

  private static final int kMod = 1_000_000_007;

  // Returns the number of paths to move the ball at (i, j) out-of-bounds with k
  // moves.
  private int findPaths(int m, int n, int k, int i, int j, Integer[][][] mem) {
    if (i < 0 || i == m || j < 0 || j == n)
      return 1;
    if (k == 0)
      return 0;
    if (mem[k][i][j] != null)
      return mem[k][i][j];
    return mem[k][i][j] = (int) ((findPaths(m, n, k - 1, i + 1, j, mem) * 1L +
                                  findPaths(m, n, k - 1, i - 1, j, mem) +
                                  findPaths(m, n, k - 1, i, j + 1, mem) +
                                  findPaths(m, n, k - 1, i, j - 1, mem)) %
                                 kMod);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def findPaths(self, m, n, maxMove, startRow, startColumn):
    kMod = 1000000007

    @functools.lru_cache(None)
    def dp(k: int, i: int, j: int) -> int:
      """
      Returns the number of paths to move the ball at (i, j) out-of-bounds with
      k moves.
      """
      if i < 0 or i == m or j < 0 or j == n:
        return 1
      if k == 0:
        return 0
      return (dp(k - 1, i + 1, j) + dp(k - 1, i - 1, j) +
              dp(k - 1, i, j + 1) + dp(k - 1, i, j - 1)) % kMod

    return dp(maxMove, startRow, startColumn)

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 dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    constexpr int kMod = 1'000'000'007;
    int ans = 0;
    // dp[i][j] := the number of paths to move the ball (i, j) out-of-bounds
    vector<vector<int>> dp(m, vector<int>(n));
    dp[startRow][startColumn] = 1;

    while (maxMove--) {
      vector<vector<int>> newDp(m, vector<int>(n));
      for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
          if (dp[i][j] > 0)
            for (const auto& [dx, dy] : dirs) {
              const int x = i + dx;
              const int y = j + dy;
              if (x < 0 || x == m || y < 0 || y == n)
                ans = (ans + dp[i][j]) % kMod;
              else
                newDp[x][y] = (newDp[x][y] + dp[i][j]) % kMod;
            }
      dp = std::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[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    final int kMod = 1_000_000_007;
    int ans = 0;
    // dp[i][j] := the number of paths to move the ball (i, j) out-of-bounds
    int[][] dp = new int[m][n];
    dp[startRow][startColumn] = 1;

    while (maxMove-- > 0) {
      int[][] newDp = new int[m][n];
      for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
          if (dp[i][j] > 0)
            for (int[] dir : dirs) {
              final int x = i + dir[0];
              final int y = j + dir[1];
              if (x < 0 || x == m || y < 0 || y == n)
                ans = (ans + dp[i][j]) % kMod;
              else
                newDp[x][y] = (newDp[x][y] + dp[i][j]) % 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
25
26
27
28
29
30
31
class Solution:
  def findPaths(
      self,
      m: int,
      n: int,
      maxMove: int,
      startRow: int,
      startColumn: int,
  ) -> int:
    dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
    kMod = 1_000_000_007
    ans = 0
    # dp[i][j] := the number of paths to move the ball (i, j) out-of-bounds
    dp = [[0] * n for _ in range(m)]
    dp[startRow][startColumn] = 1

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

    return ans