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 in any four directions(up, down, right, left) 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.

This problem is similar to Unique Paths in Grid 2-2 - Get all paths moving right or down with obstacles but robot can move in all 4 directions.

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] ]
 ]

Solution

Naive Algorithm The Naive Algorithm is to generate all paths from source to destination and one by one check if the generated path satisfies the constraints.

while there are untried paths {
       generate the next path
       if this path has all blocks as 1 {
              print this path;
       }
}

Method 1 - Backtracking Algorithm

  • We initialize result to an empty list that will eventually contain all unique valid paths.
  • We check if the starting or ending cell is an obstacle. If so, we immediately return the empty list.
  • We use a visited boolean array to make sure that we do not include any cell more than once in the same path.
  • The backtrack method explores all four directions recursively. After exploring, we undo the step (backtrack) so we can explore different paths.
  • When we reach the bottom-right corner of the grid, we add the current path to our result list.

Code

Java
public class Solution {

	public List <List<int[] >> uniquePathsWithObstacles(int[][] grid) {
		List <List<int[] >> ans = new ArrayList<>();
		int m = grid.length;
		int n = grid[0].length;
		if (grid[0][0] == 1 || grid[m - 1][n - 1] == 1) {
			return ans; // Cannot start or end on an obstacle.
		}

		boolean[][] visited = new boolean[m][n];
		backtrack(0, 0, grid, visited, new ArrayList<>(), ans);
		return ans;
	}

	private void backtrack(int row, int col, int[][] grid, boolean[][] visited, List<int[]> path, List <List<int[]>> result) {
		// Check for invalid conditions
		if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length ||
			grid[row][col] == 1 || visited[row][col]) {
			return;
		}

		// Add to path
		path.add(new int[] {
			row, col
		});
		visited[row][col] = true;

		// Check if we've reached the destination
		if (row == grid.length - 1 && col == grid[0].length - 1) {
			result.add(new ArrayList<>(path));
		} else {
			// Explore all four directions
			backtrack(row + 1, col, grid, visited, path, result); // Down
			backtrack(row - 1, col, grid, visited, path, result); // Up
			backtrack(row, col + 1, grid, visited, path, result); // Right
			backtrack(row, col - 1, grid, visited, path, result); // Left
		}

		// Remove from path and mark as unvisited for backtracking
		path.remove(path.size() - 1);
		visited[row][col] = false;
	}

	public static void main(String[] args) {
		Solution solution = new Solution();
		int[][] grid = {
			{
				0, 0, 0
			},
			{
				0, 1, 0
			},
			{
				0, 0, 0
			}
		};
		List < List<int[] >> paths = solution.uniquePathsWithObstacles(grid);

		// Print all paths
		for (List < int[] > path: paths) {
			System.out.print("Path: ");

			for (int[] step: path) {
				System.out.print("[" + step[0] + "," + step[1] + "] ");
			}

			System.out.println();
		}
	}
}

Complexity

  • ⏰ Time complexity: O(4^(m*n))
  • 🧺 Space complexity: O(m*n)