08.02. Robot in a Grid

Description

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

Solutions

Solution 1: DFS (Depth-First Search)

We can use depth-first search to solve this problem. We start from the top left corner and move right or down until we reach the bottom right corner. If at some step, we find that the current position is an obstacle, or the current position is already in the path, then we return. Otherwise, we add the current position to the path and mark the current position as visited, then continue to move right or down.

If we can finally reach the bottom right corner, then we have found a feasible path, otherwise, it means there is no feasible path.

The time complexity is $O(m \times n)$, and the space complexity is $O(m \times n)$. Here, $m$ and $n$ are the number of rows and columns of the grid, respectively.

Python3JavaC++GoTypeScriptRustSwift

class Solution:
    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List