题目

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

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

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

示例 1:

输入: grid = [[0,2],[1,3]] 输出: 3 解释: 时间为0时，你位于坐标方格的位置为 (0, 0)。 此时你不能游向任意方向，因为四个相邻方向平台的高度都大于当前时间为 0 时的水位。等时间到达 3 时，你才可以游向平台 (1, 1). 因为此时的水位是 3，坐标方格中的平台没有比水位 3 更高的，所以你可以游向坐标方格中的任意位置

示例 2:

输入: grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]] 输出: 16 解释: 最终的路线用加粗进行了标记。我们必须等到时间为 16，此时才能保证平台 (0, 0) 和 (4, 4) 是连通的

提示:

n == grid.length
n == grid[i].length
1 <= n <= 50
0 <= grid[i][j] < n^2
grid[i][j] 中每个值 均无重复

解题思路

思路一：二分查找 + 深度/广度优先搜索 (Binary Search + DFS/BFS)

这是最直观、最容易想到的思路。

核心思想

题目要求我们找到一个“最小”的时间 t。这启发我们去思考：时间 t 是否具有单调性？

如果我们在时间 t 可以从起点到达终点，那么在任何时间 t' > t 的时候，水面更高，原来能通过的路径现在也一定能通过。所以，我们也一定能到达终点。
反之，如果我们在时间 t 无法到达终点，那么在任何时间 t' < t 时，水面更低，能通过的路径更少，我们肯定也无法到达终点。

这个单调性是使用二分查找的完美信号。我们可以二分查找的不是坐标，而是时间 t (也就是最终的答案)。

算法步骤

确定二分查找的范围：
- left：最小可能的时间。我们至少要等水位没过起点 grid[0][0]，所以一个安全的下界是 0 或者 grid[0][0]。
- right：最大可能的时间。水位最高淹没所有平台即可，也就是 n*n - 1 (根据题目提示 0 <= grid[i][j] < n*n)。
- 所以，我们的答案一定在 [0, n*n - 1] 这个区间内。
进行二分查找：
- 在 while (left < right) 循环中，我们取中间值 mid = left + (right - left) / 2。
- 这个 mid 代表我们假设的“最少时间”。现在，我们需要一个函数 canReach(t) 来验证：在时间为 t (即水位高度为 t) 的时候，我们是否能从 (0, 0) 到达 (n-1, n-1)。
实现 canReach(t) 函数：
- 这个函数就是一个简单的图的连通性判断问题。
- 我们可以使用 DFS (深度优先搜索) 或 BFS (广度优先搜索) 来实现。
- 从 (0, 0) 开始遍历。一个格子 (r, c) 能被访问的前提条件是 grid[r][c] <= t。
- 使用一个 visited 数组来防止重复访问。
- 在遍历过程中，如果能成功到达 (n-1, n-1)，则 canReach(t) 返回 true。如果遍历完所有可达的格子都到不了终点，则返回 false。
根据验证结果更新二分范围：
- 如果 canReach(mid) 返回 true，说明时间 mid 是足够的（或者可能偏大）。我们想找一个更小的时间，所以我们尝试在更小的范围里寻找，令 right = mid。
- 如果 canReach(mid) 返回 false，说明时间 mid 不够，水太浅了。我们需要更多时间，令 left = mid + 1。
结束条件：
- 当 left == right 时，循环结束。此时的 left (或 right) 就是我们找到的最小的、又能保证可以到达终点的时间。

复杂度分析

时间复杂度: $O(N^2log(N^2))$ 或 $O(N^2logN)$。
- 二分查找的范围是 $N^2$，所以有 $log(N^2)$ 次迭代。
- 在每次迭代中，我们都需要做一次 DFS/BFS，最坏情况下会访问所有 $N^2$ 个格子。
空间复杂度: $O(N^2)$，用于存储 visited 数组和 DFS/BFS 的递归栈或队列。

思路二：Dijkstra 算法 / 优先队列BFS

我们可以把这个问题看作一个经典的在网格图上的最短路径问题，但是“路径的权重”定义不同。

核心思想

我们想找一条路径，使得路径上的最大值最小。这可以转化为：

状态定义：每个节点 (r, c) 的状态不仅仅是它的坐标，还包括到达这个节点所经过路径的瓶颈（即路径上的最大高度）。
目标：找到达终点 (n-1, n-1) 的所有路径中，瓶颈最小的那一条。

这非常适合使用 Dijkstra 算法。Dijkstra 算法的核心是每次都从待处理的节点中，选出“距离”最小的那个来扩展。在这里，我们把“距离”定义为“到达该节点路径上的最大高度”。

算法步骤

数据结构：
- 一个优先队列（最小堆），用于存储 (max_height, row, col)。max_height 是从起点到 (row, col) 路径上的最大平台高度，也是排序的依据。
- 一个 max_heights 数组（或哈希表），max_heights[r][c] 记录从起点到达 (r, c) 的最小瓶颈。初始化为无穷大。
初始化：
- 将起点 (grid[0][0], 0, 0) 放入优先队列。grid[0][0] 是到达起点的路径瓶颈（就是它本身）。
- 更新 max_heights[0][0] = grid[0][0]。
循环扩展：
- 当优先队列不为空时，取出堆顶元素 (h, r, c)，这是当前所有待扩展节点中瓶颈最小的。
- 如果 (r, c) 就是终点 (n-1, n-1)，那么 h 就是最终答案，直接返回。
- 遍历 (r, c) 的四个相邻节点 (nr, nc)：
  - 从 (r, c) 走到 (nr, nc)，这条新路径的瓶颈是 max(h, grid[nr][nc])，即旧瓶颈和新节点高度的较大值。
  - 如果这个新瓶颈小于之前记录的到达 (nr, nc) 的最小瓶颈（即 max(h, grid[nr][nc]) < max_heights[nr][nc]），说明我们找到了一条更优的路径到达 (nr, nc)。
  - 更新 max_heights[nr][nc] 为这个更小的新瓶颈，并将 (max(h, grid[nr][nc]), nr, nc) 加入优先队列。
结束：
- 循环直到找到终点。

复杂度分析

时间复杂度: $O(N^2log(N^2))$ 或 $O(N^2logN)$。
- 每个格子最多入队和出队一次。总共有 $N^2$ 个格子。
- 每次操作优先队列（入队或出队）的时间复杂度是 log(队列大小)，队列大小最多为 $N^2$。
空间复杂度: $O(N^2)$，用于存储 max_heights 数组和优先队列。

具体代码

这里实现的是第一个解法

    // 基本变换基
var dirs = [][]int {
    {0, 1}, {0, -1}, {1, 0}, {-1, 0},
}

func swimInWater(grid [][]int) int {

    n := len(grid)

    max := func (a, b int) int {
        if a > b {
            return a
        } else {
            return b
        }
    }
    
    // 二分
    left := max(grid[0][0], grid[n - 1][n - 1])
    right := n * n - 1

    for left < right {

        // visited数组
        visited := make([][]bool, n)
        for i := range visited {
        visited[i] = make([]bool, n)
        }

        middle := (left + right) / 2

        if dfs(0, 0, visited, grid, middle) {
            right = middle
        } else {
            left = middle + 1
        }

    }
    return left
}

func dfs(row, col int, visited [][]bool, grid [][]int, level int) bool {

    visited[row][col] = true

    n := len(visited)

    // 如果已经到了右下角
    if visited[n - 1][n - 1] {
        return true
    }

    for _, dir := range dirs {

        new_row := row + dir[0]
        new_col := col + dir[1]

        // 检查越界
        if new_row < 0 || new_row >= n || new_col < 0 || new_col >= n {
            continue
        }

        // 检查是否访问
        if visited[new_row][new_col] {
            continue
        }

        // 检查连通性条件
        if level < grid[new_row][new_col] {
            continue
        }

        // 传导
        if dfs(new_row, new_col, visited, grid, level) {
            return true
        }
    }

    return false
}

beautifulremi / 778. 水位上升的泳池中游泳

题目

解题思路

思路一：二分查找 + 深度/广度优先搜索 (Binary Search + DFS/BFS)

核心思想

算法步骤

复杂度分析

思路二：Dijkstra 算法 / 优先队列BFS

核心思想

算法步骤

复杂度分析

具体代码