Imagine a robot sitting on the upper left corner of grid with r rows and c columns. The robot can only move in two directions, right and down, but certain cells are "off limits" such that the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to the bottom right.
"off limits" and empty grid are represented by 1 and 0 respectively.
Return a valid path, consisting of row number and column number of grids in the path.
Example 1:
Input: [ [0,0,0], [0,1,0], [0,0,0] ] Output: [[0,0],[0,1],[0,2],[1,2],[2,2]]
Note:
r, c <= 100
function pathWithObstacles(obstacleGrid: number[][]): number[][] {
const m = obstacleGrid.length;
const n = obstacleGrid[0].length;
const res = [];
const dfs = (i: number, j: number): boolean => {
if (i === m || j === n || obstacleGrid[i][j] === 1) {
return false;
}
res.push([i, j]);
obstacleGrid[i][j] = 1;
if ((i + 1 === m && j + 1 === n) || dfs(i + 1, j) || dfs(i, j + 1)) {
return true;
}
res.pop();
return false;
};
if (dfs(0, 0)) {
return res;
}
return [];
}impl Solution {
fn dfs(grid: &mut Vec<Vec<i32>>, path: &mut Vec<Vec<i32>>, i: usize, j: usize) -> bool {
if i == grid.len() || j == grid[0].len() || grid[i][j] == 1 {
return false;
}
path.push(vec![i as i32, j as i32]);
grid[i as usize][j as usize] = 1;
if (i + 1 == grid.len() && j + 1 == grid[0].len())
|| Self::dfs(grid, path, i + 1, j)
|| Self::dfs(grid, path, i, j + 1)
{
return true;
}
path.pop();
false
}
pub fn path_with_obstacles(mut obstacle_grid: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let mut res = vec![];
if Self::dfs(&mut obstacle_grid, &mut res, 0, 0) {
return res;
}
vec![]
}
}