难度: Medium
设想有个机器人坐在一个网格的左上角，网格 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。
运行时间: 23 ms
内存: 16.6 MB
class Solution:
def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:
ans, r, c = [], len(obstacleGrid), len(obstacleGrid[0])
if obstacleGrid[-1][-1] != 0:
return ans
obstacleGrid[-1][-1] = 2
for i in range(r-1, -1, -1):
for j in range(c-1, -1, -1):
if obstacleGrid[i][j] > 1:
if i > 0 and not obstacleGrid[i - 1][j]:
obstacleGrid[i - 1][j] = 2
if j > 0 and not obstacleGrid[i][j - 1]:
obstacleGrid[i][j - 1] = 3
if obstacleGrid[0][0] > 1:
i, j = 0, 0
while i < r and j < c:
ans.append([i, j])
if obstacleGrid[i][j] == 2:
i += 1
else:
j += 1
return ans
这个题解首先判断右下角是否有障碍，如果有，则直接返回空路径。若没有障碍，从右下角开始，逆向考虑每个位置是否可以到达。使用标记值2代表可以向下走到达终点，标记值3代表可以向右走到达终点。这个标记过程是一个逆向的动态规划过程。开始于右下角，向左上角逆推，每个格子根据其右侧和下方的格子的标记来确定自己的标记。最后，如果左上角的格子被标记为可行（标记值大于1），则构造路径。路径的构造是根据每个格子的标记决定下一步是向下还是向右移动。
时间复杂度: O(r*c)
空间复杂度: O(r*c)
class Solution:
def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:
ans, r, c = [], len(obstacleGrid), len(obstacleGrid[0])
# 如果终点有障碍物, 直接返回空路径
if obstacleGrid[-1][-1] != 0:
return ans
# 标记终点可达
obstacleGrid[-1][-1] = 2
# 从右下角向左上角标记可达路径
for i in range(r-1, -1, -1):
for j in range(c-1, -1, -1):
if obstacleGrid[i][j] > 1:
if i > 0 and not obstacleGrid[i - 1][j]:
obstacleGrid[i - 1][j] = 2
if j > 0 and not obstacleGrid[i][j - 1]:
obstacleGrid[i][j - 1] = 3
# 如果起点可达, 构造路径
if obstacleGrid[0][0] > 1:
i, j = 0, 0
while i < r and j < c:
ans.append([i, j])
if obstacleGrid[i][j] == 2:
i += 1
else:
j += 1
return ans
在这个题解中，我们的目标是确认从左上角到右下角是否存在一条可行的路径。由于我们的路径构建是从右下角向左上角逆推的，如果右下角本身有障碍物，那么无论其他位置如何，路径都是不可达的。因此，检查右下角是为了立即决定是否终止算法，避免不必要的计算。
题解实际上没有考虑一个格子同时可以向下和向右行走的情形。标记值2和3仅表示首个可行的方向。在实现中，如果发现一个格子同时可以向下和向右行走，它将首先被标记为向下行走（标记值2）。只有当向下不可行时，它才可能被标记为向右行走（标记值3）。这种处理方式简化了逻辑，但可能不会探索所有可能的路径。
题解中通过循环的起始和终止条件来保证不会访问网格之外的元素。对于行和列的遍历，都是从网格的最后一个索引开始，递减至0。在检查相邻的格子（向左或向上的格子）时，会首先检查索引是否大于0，确保不会访问到网格的边界之外。这种方式可以有效避免数组越界错误。