Problem Statement in English

You’re given a 2D grid of integers, where each cell represents the health cost to step on that cell.

You start at the top-left corner of the grid and want to reach the bottom-right corner.

You have a certain amount of health, and you can only move to any of your 4 adjacent cells.

Your task is to determine if there exists a path from the top-left corner to the bottom-right corner such that your health never drops below 1 at any point along the path.

If you enter a cell with a value of 0 , your health remains the same. If you enter a cell with a value of 1, your health decreases by 1.

Return true if such a path exists, otherwise return false.

Approach

You can either solve this with a breadth first search or using a priority queue (min-heap) to always explore the path with the highest remaining health first.

In the first approach you’ll need to keep track of the remaining health at each cell and use a queue to explore all possible paths. You only revisit a path if you have more health than the last time you visited that cell.

In the second approach, you can use a min-heap to always explore the path with the highest remaining health first. This way, you can quickly determine if a safe path exists without exploring all possible paths.

And we’re done!

Solution in Python


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

        minheap = [(-(health - grid[0][0]), 0, 0)]
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        seen = set()

        while minheap:
            h, x, y = heappop(minheap)
            h *= -1

            if x == M - 1 and y == N - 1 and h >= 1: return True

            if (x, y) in seen: continue
            seen.add((x, y))

            for dx, dy in directions:
                nx, ny = x + dx, y + dy

                if 0 <= nx < M and 0 <= ny < N and (nx, ny) not in seen:
                    nh = h - grid[nx][ny]
                    if nh < 1: continue
                    heappush(minheap, (-nh, nx, ny))

        return False

Complexity

  • Time: $O(MN \log(MN))$

  • Space: $O(MN)$

And we are done.