题目难度: 中等
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
设想有个机器人坐在一个网格的左上角，网格 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。
题目思考
- 如何根据前面的坐标得出能否到达当前坐标?
- 如何求出最终路径?
解决方案
思路
- 分析题目, 机器人只能向下或向右移动, 我们可以利用这一点, 根据当前坐标的左边和上边相邻坐标的可达性来判断当前坐标是否可达
- 显然这就是动态规划的思路:
- 设 dp[r][c] 代表能否到达坐标(r,c)
- 初始化 dp[0][0] = True (前提是左上角是 0), 其他值全是 False, 表示开始时只有起点可达
- 然后根据当前坐标的值来进行状态转移:
- 如果当前坐标值是 0, dp[r][c] = dp[r-1][c] | dp[r][c-1], 表示如果左边和上边相邻坐标任何一个可达, 就能到达当前坐标
- 如果当前坐标值是 1, 则跳过它, 不可能到达
- 最终右下角坐标的 dp 值就代表是否能到达它
- 判断完可达性之后, 我们还需要求出可行路径, 这里可以采用倒推的方式, 具体做法如下:
- 从右下角开始, 找左边或上边相邻的 dp 值是 True 的坐标
- 找到后将其加入结果列表, 并作为新的坐标继续遍历
- 最终遍历到左上角结束, 此时列表的逆序就是一条可行的路径
- 下面代码对应的就是上面整个过程, 并加入了必要的注释, 方便大家理解
复杂度
- 时间复杂度 O(MN): 需要遍历整个网格(M 和 N 分别是行数和列数)
- 空间复杂度 O(MN): 需要额外的二维 dp 数组
代码
Python 3
class Solution:
def pathWithObstacles(self, obstacleGrid: List[List[int]]) -> List[List[int]]:
# 动态规划存是否可达+倒推找有效路径
if not obstacleGrid or obstacleGrid[0][0] == 1:
# 空网格或者起点有障碍, 没有可行路径
return []
rows, cols = len(obstacleGrid), len(obstacleGrid[0])
dp = [[False] * cols for _ in range(rows)]
dp[0][0] = True
for r in range(rows):
for c in range(cols):
if obstacleGrid[r][c] == 0:
if r - 1 >= 0:
dp[r][c] |= dp[r - 1][c]
if c - 1 >= 0:
dp[r][c] |= dp[r][c - 1]
if not dp[rows - 1][cols - 1]:
# 不能到达右下角, 没有可行路径
return []
# 倒推找有效路径
r, c = rows - 1, cols - 1
res = [[r, c]]
while r != 0 or c != 0:
if r - 1 >= 0 and dp[r - 1][c]:
# 路径可以向上
r -= 1
elif c - 1 >= 0 and dp[r][c - 1]:
# 路径只能向左
c -= 1
res.append([r, c])
return res[::-1] 大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号