摘要
Title: 3286. 穿越网格图的安全路径
Categories: 双端队列广搜、dfs

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] + g
                        if 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)]

        @cache
        def 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 False
            
            visited[i][j] = True
            h -= grid[i][j]

            if i == m - 1 and j == n - 1 and h > 0:
                return True

            if (dfs(i - 1, j, h) or  # 上
                dfs(i, j - 1, h) or  # 左
                dfs(i, j + 1, h) or  # 右
                    dfs(i + 1, j, h)):   # 下
                return True

            visited[i][j] = False
            return False

        return dfs(0, 0, health)