面试题 08.02. 迷路的机器人

设想有个机器人坐在一个网格的左上角，网格 r 行 c 列。机器人只能向下或向右移动，但不能走到一些被禁止的网格（有障碍物）。设计一种算法，寻找机器人从左上角移动到右下角的路径。

网格中的障碍物和空位置分别用 1 和 0 来表示。

返回一条可行的路径，路径由经过的网格的行号和列号组成。左上角为 0 行 0 列。如果没有可行的路径，返回空数组。

示例 1:

输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: [[0,0],[0,1],[0,2],[1,2],[2,2]]
解释:
输入中标粗的位置即为输出表示的路径，即
0行0列（左上角） -> 0行1列 -> 0行2列 -> 1行2列 -> 2行2列（右下角）
说明：r 和 c 的值均不超过 100。

Python 解答：
1.回溯

class Solution:
    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:
        if obstacleGrid[0][0]:
            return []
        lis = []     
        res = [[0,0]]   
        def dfs(obstacleGrid, x, y, res):
            if x == len(obstacleGrid)-1 and y == len(obstacleGrid[0])-1:
                nonlocal lis
                lis.append(res)
                return 
            temp = []
            if x+1 < len(obstacleGrid) and obstacleGrid[x+1][y] == 0:
                temp.append([x+1, y])
            if y+1 < len(obstacleGrid[0]) and obstacleGrid[x][y+1] == 0:
                temp.append([x, y+1])
            for item in temp:
                res.append(item)
                obstacleGrid[item[0]][item[1]] = 1
                dfs(obstacleGrid, item[0], item[1], res[::])
                res.pop()
        dfs(obstacleGrid, 0, 0, res)
        return lis[0] if lis else []

2.动态规划

class Solution:
    def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:
        matrix = [[0 for i in range(len(obstacleGrid[0]))] for j in range(len(obstacleGrid))]
        pre = 1
        for i in range(len(matrix)):
            if obstacleGrid[i][0] == 1:
                matrix[i][0] = 0
                pre = matrix[i][0]
            else:
                matrix[i][0] = pre
        pre = 1
        for i in range(len(matrix[0])):
            if obstacleGrid[0][i] == 1:
                matrix[0][i] = 0
                pre = matrix[0][i]
            else:
                matrix[0][i] = pre
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                if obstacleGrid[i][j] == 1:
                    matrix[i][j] = 0
                else:
                    matrix[i][j] = matrix[i-1][j]+matrix[i][j-1]
        res = []
        if matrix[-1][-1]:
            i, j = len(matrix)-1, len(matrix[0])-1
            while i != 0 or j != 0:
                res.append([i, j])
                if i > 0 and matrix[i-1][j]:
                    i -= 1
                elif j > 0 and matrix[i][j-1]:
                    j -= 1
                elif i == 0 and j > 0:
                    j -= 1
                elif j == 0 and i > 0:
                    i -= 1
            res.append([0, 0])
            return res[::-1]
        else:
            return []