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 False
        q = [(-health+grid[0][0], 0, 0)]
        seen = set()
        while q:
            h, x, y = heapq.heappop(q)
            if (x, y) in seen:
                continue
            seen.add((x, y))
            h = -h
            for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                nx, ny = x+dx, y+dy
                if 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 True
                    heapq.heappush(q, (-(h-grid[nx][ny]), nx, ny))
        return False

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