钦州市建设网站,做机械比较好的外贸网站,投诉网站建设,企业建设门户网站的需求Leetcode 3286. Find a Safe Walk Through a Grid 1. 解题思路2. 代码实现 题目链接#xff1a;3286. Find a Safe Walk Through a Grid
1. 解题思路
这一题的话思路上就是一个宽度优先遍历#xff0c;我们按照health进行排序进行宽度优先遍历#xff0c;看看在health被消…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 [(-healthgrid[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 xdx, ydyif 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。
