26.01.2024
576. Out of Boundary Paths medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/484
Problem TLDR
Number of paths from cell in grid to out of boundary.
Intuition
Let’s do a Brute-Force Depth-First Search from the current cell to neighbors. If we are out of boundary, we have a 1
path, and 0
if moves are out. Then add memoization with a HashMap.
Approach
using
long
helps to shorten the code
Complexity
Time complexity:
O(nmv)Space complexity:
O(nmv)
Code
fun findPaths(m: Int, n: Int, maxMove: Int, startRow: Int, startColumn: Int): Int {
val dp = mutableMapOf<Pair<Pair<Int, Int>, Int>, Long>()
fun dfs(y: Int, x: Int, move: Int): Long = dp.getOrPut(y to x to move) {
if (y < 0 || x < 0 || y == m || x == n) 1L
else if (move <= 0) 0L else
dfs(y - 1, x, move - 1) +
dfs(y + 1, x, move - 1) +
dfs(y, x - 1, move - 1) +
dfs(y, x + 1, move - 1) } % 1_000_000_007L
return dfs(startRow, startColumn, maxMove).toInt()
}
pub fn find_paths(m: i32, n: i32, max_move: i32, start_row: i32, start_column: i32) -> i32 {
let mut dp = HashMap::new();
fn dfs( y: i32, x: i32, mov: i32, m: i32, n: i32, dp: &mut HashMap<(i32, i32, i32), i64> ) -> i64 {
if y < 0 || x < 0 || y == m || x == n { 1 } else if mov<= 0 { 0 } else {
if let Some(&cache) = dp.get(&(y, x, mov)) { cache } else {
let result = (dfs(y - 1, x, mov - 1, m, n, dp) +
dfs(y + 1, x, mov - 1, m, n, dp) +
dfs(y, x - 1, mov - 1, m, n, dp) +
dfs(y, x + 1, mov - 1, m, n, dp)) % 1_000_000_007;
dp.insert((y, x, mov), result); result
}
}
}
dfs(start_row, start_column, max_move, m, n, &mut dp) as i32
}