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();
		}
	}
}