Leetcode 3286. Find a Safe Walk Through a Grid

• Leetcode 3286. Find a Safe Walk Through a Grid
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3286. Find a Safe Walk Through a Grid

1. 解题思路

这一题的话思路上就是一个宽度优先遍历，我们按照health进行排序进行宽度优先遍历，看看在health被消耗完之前是否可能走到终点即可。

2. 代码实现

给出python代码实现如下：

class Solution:def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:n, m = len(grid), len(grid[0])if health - grid[0][0] < 1:return Falseq = [(-health+grid[0][0], 0, 0)]seen = set()while q:h, x, y = heapq.heappop(q)if (x, y) in seen:continueseen.add((x, y))h = -hfor dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:nx, ny = x+dx, y+dyif 0 <= nx < n and 0 <= ny < m and (nx, ny) not in seen and h - grid[nx][ny] > 0:if nx == n-1 and ny == m-1:return Trueheapq.heappush(q, (-(h-grid[nx][ny]), nx, ny))return False

提交代码评测得到：耗时238ms，占用内存17.3MB。