# 778.水位上升的泳池中游泳 (Hard)

## 问题描述
[778. 水位上升的泳池中游泳 (Hard)](https://leetcode.cn/problems/swim-in-rising-water/)

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

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

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

**示例 1:**

![](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-65504.jpg)

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

```

**示例 2:**

![](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-065505.jpg)

```
输入: 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²`
- `grid[i][j]` 中每个值 **均无重复**

## 解题思路
### 二分+bfs
二分答案，然后利用bfs判断这个等待时间下，能否到达终点：
- 无法到达终点，说明`mid < ans`，则`left = mid + 1`；
- 可以到达终点，说明`mid >= ans`，则`right = mid`；

### dijkstra
堆优化的**dijkstra**，使用小顶堆，每次入队的是当前时间与`grid[i][j]`的最大值。

## 代码
### 二分+bfd
```cpp
class Solution {
  public:
    bool bfs(vector<vector<int>> &grid, int mid) {
        int n = grid.size();
        vector<vector<int>> vis(n, vector<int>(n, 0));
        queue<vector<int>> q;
        q.push({0, 0});
        vis[0][0] = 1;
        vector<vector<int>> mov{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        while (!q.empty()) {
            auto vec = q.front();
            if (vec[0] == n - 1 && vec[1] == n - 1) {
                return true;
            }
            q.pop();
            for (int i = 0; i < 4; ++i) {
                int x_new = vec[0] + mov[i][0], y_new = vec[1] + mov[i][1];
                if (x_new >= 0 && x_new < n && y_new >= 0 && y_new < n && vis[x_new][y_new] == 0 && mid >= grid[x_new][y_new]) {
                    q.push({x_new, y_new});
                    vis[x_new][y_new] = 1;
                }
            }
        }
        return false;
    }
    int swimInWater(vector<vector<int>> &grid) {
        // 二分答案，如果ans < target，那么无法到达，左闭右开
        int left = 0, right = 2500;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (bfs(grid, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return std::max(left, grid[0][0]);
    }
};
```

### dijsktra
```cpp
class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        // Dijkstra算法
        int n = grid.size();
        auto cmp = [&](vector<int> &v1, vector<int> &v2) {
            return v1[2] > v2[2];
        };
        priority_queue<vector<int> , vector<vector<int>>, decltype(cmp)> pq(cmp);
        pq.push({0, 0, grid[0][0]}); // 从0时刻出发，0，0坐标出发
        vector<vector<int>> dis(n, vector<int>(n, -1));
        vector<vector<int>> mov{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        while (!pq.empty()) {
            auto vec = pq.top();
            int x = vec[0], y = vec[1], time = vec[2];
            pq.pop();
            if (dis[x][y] != -1) {
                continue;
            }
            dis[x][y] = time;
            for (int i = 0; i < 4; ++i) {
                int new_x = x + mov[i][0], new_y = y + mov[i][1];
                if (new_x >= 0 && new_x < n && new_y >= 0 && new_y < n) {
                    if (dis[new_x][new_y] == -1) {
                        if (time >= grid[new_x][new_y]) {
                            pq.push({new_x, new_y, time});
                        } else {
                            pq.push({new_x, new_y, grid[new_x][new_y]});
                        }
                    }
                }
            }
        }
        return dis[n - 1][n - 1];
    }
};
```