Leetcode 794 Solution

This article provides solution to leetcode question 794 (swim-in-rising-water)
Categories:
Tags:
Access this page by simply typing in "lcs 794" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/swim-in-rising-water

Solution

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)

        ans = grid[0][0]
        heap = [(ans, (0, 0))]

        while heap:
            v, (i, j) = heapq.heappop(heap)
            ans = max(v, ans)

            if i == n - 1 and j == n - 1:
                return ans

            if i > 0 and grid[i - 1][j] != -1:
                heapq.heappush(heap, (grid[i - 1][j], (i - 1, j)))
                grid[i - 1][j] = -1

            if i < n - 1 and grid[i + 1][j] != -1:
                heapq.heappush(heap, (grid[i + 1][j], (i + 1, j)))
                grid[i + 1][j] = -1

            if j > 0 and grid[i][j - 1] != -1:
                heapq.heappush(heap, (grid[i][j - 1], (i, j - 1)))
                grid[i][j - 1] = -1

            if j < n - 1 and grid[i][j + 1] != -1:
                heapq.heappush(heap, (grid[i][j + 1], (i, j + 1)))
                grid[i][j + 1] = -1

        return ans