1.题目基本信息

1.1.题目描述

在一个 n x n 的整数矩阵 grid 中，每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。

当开始下雨时，在时间为 t 时，水池中的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。

你从坐标方格的左上平台 (0，0) 出发。返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间 。

1.2.题目地址

https://leetcode.cn/problems/swim-in-rising-water/description/

2.解题方法

2.1.解题思路

二分+广度优先搜索 / Dijkstra算法(将路径权重更换为路径中的最大值)

2.2.解题步骤

思路1：二分+广度优先搜索

• 第一步，构建二分检查函数，该函数实现检查t时刻，是否存在路径，从起点node到达终点(n-1,n-1)

• 第二步，二分找到最小的t使check通过

3.解题代码

python代码-Dijkstra算法

from heapq import heappush, heappop

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        # 思路2：Dijkstra算法。将路径权重更换为路径中的最大值
        n = len(grid)
        heap = [(grid[0][0], 0)]
        weights = [inf] * (n * n)
        weights[0] = grid[0][0]
        while heap:
            weight, node = heappop(heap)
            if node == n * n - 1:
                return weight
            if weight > weights[node]:
                continue
            r, c = node // n, node % n
            for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nr, nc = r + dr, c + dc
                nnode = nr * n + nc
                if 0 <= nr < n and 0 <= nc < n:
                    newWeight = max(weight, grid[nr][nc])
                    if weights[nnode] > newWeight:
                        heappush(heap, (newWeight, nnode))
                        weights[nnode] = newWeight
        return -1

python代码-二分+广度优先搜索

from collections import deque

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        # 思路1：二分+广度优先搜索
        n = len(grid)
        if n == 1:
            return 0
        # 第一步，构建二分检查函数，该函数实现检查t时刻，是否存在路径，从起点node到达终点(n-1,n-1)
        def check(t:int) -> bool:
            if grid[0][0] > t:
                return False
            que = deque([0])
            visited = set([0])
            while que:
                for _ in range(len(que)):
                    node = que.popleft()
                    if node == n * n - 1:
                        return True
                    r, c = node // n, node % n
                    for dr, dc in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
                        nr, nc = r + dr, c + dc
                        nnode = nr * n + nc
                        if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] <= t and nnode not in visited:
                            que.append(nnode)
                            visited.add(nnode)
            return False
        # 第二步，二分找到最小的t使check通过
        left, right = 1, n * n - 1
        while left <= right:
            mid = (right - left) // 2 + left
            if check(mid):
                right = mid - 1
            else:
                left = mid + 1
        return left

4.执行结果