Interview question 08.02 Lost robot

topic

Imagine a robot sitting in the upper left corner of a grid , grid r That's ok c Column . The robot can only move down or right , But you can't go to some forbidden grid （ There are obstacles ）. Design an algorithm , Find the path for the robot to move from the upper left corner to the lower right corner .

Obstacles and empty positions in the grid are used respectively 1 and 0 To express .

Return to a feasible path , The path consists of the row and column numbers of the passing grid . The upper left corner of 0 That's ok 0 Column . If there is no feasible path , Return an empty array .

Example  1:

Input :
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output : [[0,0],[0,1],[0,2],[1,2],[2,2]]
explain :
The position marked with bold in the input is the path represented by the output , namely
0 That's ok 0 Column （ top left corner ） -> 0 That's ok 1 Column -> 0 That's ok 2 Column -> 1 That's ok 2 Column -> 2 That's ok 2 Column （ The lower right corner ）

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/robot-in-a-grid-lcci
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking

It depends on the question Can only go down and right ！！！！！ dfs Can be

Code

class Solution:
    def __init__(self):
        self.r = 0
        self.c = 0
        self.ans = []

    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:
        self.r = len(obstacleGrid)
        self.c = len(obstacleGrid[0])
        self.findPath(0,0,obstacleGrid)
        return self.ans

    def findPath(self, x: int, y: int, obstacleGrid: List[List[int]]) -> bool:
        if x < 0 or x >= self.r or y < 0 or y >= self.c or obstacleGrid[x][y] == 1:
            return False
        self.ans.append([x, y])
        if x == self.r - 1 and y == self.c - 1:
            return True
        obstacleGrid[x][y] = 1
        ok = self.findPath(x + 1, y, obstacleGrid) or self.findPath(x, y + 1, obstacleGrid)
        if not ok:
            self.ans.pop()
        return ok