Problem
You are given an m x n
integer array grid
. There is a robot initially located at the top-left corner (i.e., grid[0][0]
). The robot tries to move to the bottom-right corner (i.e., grid[m-1][n-1]
). The robot can only move either down or right at any point in time.
An obstacle and space are marked as 1
or 0
respectively in grid
. A path that the robot takes cannot include any square that is an obstacle.
Return all possible unique paths that the robot can take to reach the bottom-right corner.
Examples
Example 1:
There is one obstacle in the middle of a 3x3 grid as illustrated below.
Input:
obstacleGrid =[[0,0,0],[0,1,0],[0,0,0]]
Output:
[
[[0, 0], [0, 1], [0, 2], [1, 2], [2, 2]],
[[0, 0], [1, 0], [2, 0], [2, 1], [2, 2]]
]
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
Example 2:
Input:
obstacleGrid =[[0,1],[0,0]]
Output:
[
[[0, 0], [1, 0], [1, 1]]
]
Note: m and n will be at most 100.
Solution
Method 1 - Backtracking Algorithm
We traverse the grid while maintaining a current path. If we encounter an obstacle or the edge of the grid, we backtrack and try a different direction. When we reach the bottom-right corner, we add the current path to our list of paths. We can do following:
- We have a boolean matrix
visited
to track which cells in the grid have been visited during the current path exploration to prevent revisiting them. - The
dfs
function recursively explores each possible path. At each step, it marks the current cell as visited, adds its coordinate to the current path, and then calls itself to move right or down. - When the bottom-right corner is reached, the current path is added to the list of all paths.
- After each call to
dfs
, we backtrack: we unmark the current cell and remove it from the current path.
Code
Java
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<List<int[]>> uniquePathsWithObstacles(int[][] obstacleGrid) {
List <List<int[]>> paths = new ArrayList<>();
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) {
return paths; // Can't start or end on an obstacle
}
boolean[][] visited = new boolean[m][n];
dfs(obstacleGrid, visited, 0, 0, new ArrayList<>(), paths);
return paths;
}
private void dfs(int[][] grid, boolean[][] visited, int i, int j, List <int[]> currentPath, List < List<int[] >> paths) {
// Check boundaries and obstacles
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 1 || visited[i][j]) {
return;
}
visited[i][j] = true;
currentPath.add(new int[] {
i, j
});
// Check if we've reached the destination
if (i == grid.length - 1 && j == grid[0].length - 1) {
paths.add(new ArrayList<>(currentPath)); // Add current path to paths
} else {
// Explore further paths
dfs(grid, visited, i + 1, j, currentPath, paths); // Down
dfs(grid, visited, i, j + 1, currentPath, paths); // Right
}
// Backtrack
visited[i][j] = false;
currentPath.remove(currentPath.size() - 1);
}
public static void main(String[] args) {
Solution solution = new Solution();
int[][] obstacleGrid = {
{
0, 0, 0
},
{
0, 1, 0
},
{
0, 0, 0
}
};
List < List<int[] >> paths = solution.uniquePathsWithObstacles(obstacleGrid);
// Print all paths
for (List < int[] > path: paths) {
for (int[] step: path) {
System.out.print("[" + step[0] + "," + step[1] + "] ");
}
System.out.println();
}
}
}