Powered by:NEFU AB-IN
Link
文章目录
- 3286. 穿越网格图的安全路径
- 题意
- 思路
- 代码
3286. 穿越网格图的安全路径
题意
给你一个 m x n 的二进制矩形 grid 和一个整数 health 表示你的健康值。
你开始于矩形的左上角 (0, 0) ，你的目标是矩形的右下角 (m - 1, n - 1) 。
你可以在矩形中往上下左右相邻格子移动，但前提是你的健康值始终是 正数 。
对于格子 (i, j) ，如果 grid[i][j] = 1 ，那么这个格子视为 不安全 的，会使你的健康值减少 1 。
如果你可以到达最终的格子，请你返回 true ，否则返回 false 。
注意 ，当你在最终格子的时候，你的健康值也必须为 正数 。
思路
-
双端队列广搜
当值只有01时使用，0放队首，1放对尾 -
记忆化搜索
正常dfs，当dfs一条路径时，记录哪些地方走过了，之后回溯，然后不走不符合要求的地方
代码
class Solution:def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:m, n = len(grid), len(grid[0])dis = [[inf] * n for _ in range(m)]dis[0][0] = grid[0][0]q = deque([(0, 0)])while q:i, j = q.popleft()for x, y in (i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j):if 0 <= x < m and 0 <= y < n:g = grid[x][y]if dis[i][j] + g < dis[x][y]:dis[x][y] = dis[i][j] + gif g == 0:q.appendleft((x, y))else:q.append((x, y))return dis[-1][-1] < health
class Solution:def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:m, n = len(grid), len(grid[0])visited = [[False] * n for _ in range(m)]@cachedef dfs(i: int, j: int, h: int) -> bool:if not (0 <= i < m) or not (0 <= j < n) or h <= 0 or visited[i][j]:return Falsevisited[i][j] = Trueh -= grid[i][j]if i == m - 1 and j == n - 1 and h > 0:return Trueif (dfs(i - 1, j, h) or # 上dfs(i, j - 1, h) or # 左dfs(i, j + 1, h) or # 右dfs(i + 1, j, h)): # 下return Truevisited[i][j] = Falsereturn Falsereturn dfs(0, 0, health)
