Leetcode 3286. Find a Safe Walk Through a Grid

leetcode

목록 보기

200/201

문제

You are given an m x n binary matrix grid and an integer health.

You start on the upper-left corner (0, 0) and would like to get to the lower-right corner (m - 1, n - 1).

You can move up, down, left, or right from one cell to another adjacent cell as long as your health remains positive.

Cells (i, j) with grid[i][j] = 1 are considered unsafe and reduce your health by 1.

Return true if you can reach the final cell with a health value of 1 or more, and false otherwise.

m x n 크기의 이진 행렬 grid와 정수 health가 주어집니다.

당신은 좌측 상단 모서리인 (0, 0)에서 시작하여 우측 하단 모서리인 (m - 1, n - 1)에 도달하려고 합니다.

상하좌우로 인접한 셀로 이동할 수 있으며, 이동 후에도 체력이 양수로 남아 있어야 합니다.

grid[i][j] = 1인 셀은 위험한 셀로 간주되며, 해당 셀에 들어가면 체력이 1 감소합니다.

최종 셀에 체력 1 이상으로 도달할 수 있다면 true를 반환하고, 그렇지 않다면 false를 반환하세요.

예시

Input: grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]], health = 1

0, 0 부터ㅏ 2, 4까지 체력을 전혀 쓰지 않고 갈수 있다.

제한

$m == grid.length$
$n == grid[i].length$
$1 <= m, n <= 50$
$2 <= m * n$
$1 <= health <= m + n$
grid의 값은 0 혹은 1이다.

풀이

from heapq import heappop_max, heappush_max


class Solution:
    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:
        ROW = len(grid)
        COL = len(grid[0])

        visit = [[0] * COL for _ in range(ROW)]
        visit[0][0] = health if grid[0][0] != 1 else health - 1
        if visit[0][0] <= 0:
            return False

        heap = [(visit[0][0], 0, 0)]
        d = [[-1, 0], [1, 0], [0, -1], [0, 1]]

        def bound(r: int, c: int) -> bool:
            return 0 <= r < ROW and 0 <= c < COL

        while heap:
            h, r, c = heappop_max(heap)

            if r == ROW - 1 and c == COL - 1:
                return True

            for dr, dc in d:
                tr, tc = r + dr, c + dc

                if not bound(tr, tc):
                    continue

                next_health = h - 1 if grid[tr][tc] == 1 else h

                if next_health <= visit[tr][tc]:
                    continue

                visit[tr][tc] = next_health

                heappush_max(heap, (h - 1 if grid[tr][tc] == 1 else h, tr, tc))

        return False