Hard

题目描述

给定一个 n x n 的整数矩阵 grid，其中每个值 grid[i][j] 表示该点 (i, j) 的高度。

开始下雨，随着时间推移，水位逐渐上升。在时间 t，水位为 t，这意味着任何高度小于等于 t 的格子都被淹没或可达。

当且仅当两个相邻格子的高度都不超过 t 时，你才能从一个格子游泳到另一个四方向相邻的格子。你可以在零时间内游任意距离。当然，在游泳过程中你必须待在网格的边界内。

如果你从左上角的格子 (0, 0) 开始，返回能够到达右下角的格子 (n-1, n-1) 的最少时间。

示例 1:

输入: grid = [[0,2],[1,3]]
输出: 3
解释:
时间为0时，你在格子 (0, 0)。
你不能游到其他地方，因为四方向相邻的邻居都有更高的高度，超过了 t = 0。
直到时间为3，你才能到达格子 (1, 1)。
当水的深度为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²
  • grid[i][j] 中的每个值都是唯一的

解题思路

这道题可以用多种方法求解，核心思想是找到最小的时间 t，使得从 (0,0) 到 (n-1,n-1) 存在一条路径，路径上所有格子的高度都不超过 t。

方法一：二分搜索 + BFS/DFS（推荐）

由于题目要求最小时间，且时间具有单调性（时间越大，能到达的区域越多），可以使用二分搜索。对于每个候选时间 t，使用 BFS 或 DFS 检查是否能从起点到达终点。

方法二：Dijkstra 算法

将问题转化为最短路径问题。每个格子作为图中的节点，相邻格子之间的边权重为两个格子高度的最大值。使用优先队列实现 Dijkstra 算法，找到从起点到终点的最小路径权重。

方法三：并查集

按高度从小到大遍历所有格子，逐步加入可通行区域。当起点和终点连通时，当前高度就是答案。

下面给出 Dijkstra 算法的实现，它在实际应用中通常表现最好。

代码实现

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> dist(n, vector<int>(n, INT_MAX));
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
        
        dist[0][0] = grid[0][0];
        pq.push({grid[0][0], 0, 0});
        
        vector<vector<int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        
        while (!pq.empty()) {
            auto curr = pq.top();
            pq.pop();
            
            int time = curr[0], x = curr[1], y = curr[2];
            
            if (x == n - 1 && y == n - 1) {
                return time;
            }
            
            if (time > dist[x][y]) continue;
            
            for (auto& dir : directions) {
                int nx = x + dir[0], ny = y + dir[1];
                
                if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                    int newTime = max(time, grid[nx][ny]);
                    
                    if (newTime < dist[nx][ny]) {
                        dist[nx][ny] = newTime;
                        pq.push({newTime, nx, ny});
                    }
                }
            }
        }
        
        return -1;
    }
};

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        import heapq
        
        n = len(grid)
        dist = [[float('inf')] * n for _ in range(n)]
        pq = [(grid[0][0], 0, 0)]
        dist[0][0] = grid[0][0]
        
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        while pq:
            time, x, y = heapq.heappop(pq)
            
            if x == n - 1 and y == n - 1:
                return time
            
            if time > dist[x][y]:
                continue
            
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                
                if 0 <= nx < n and 0 <= ny < n:
                    new_time = max(time, grid[nx][ny])
                    
                    if new_time < dist[nx][ny]:
                        dist[nx][ny] = new_time
                        heapq.heappush(pq, (new_time, nx, ny))
        
        return -1

public class Solution {
    public int SwimInWater(int[][] grid) {
        int n = grid.Length;
        int[,] dist = new int[n, n];
        var pq = new PriorityQueue<(int time, int x, int y), int>();
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i, j] = int.MaxValue;
            }
        }
        
        dist[0, 0] = grid[0][0];
        pq.Enqueue((grid[0][0], 0, 0), grid[0][0]);
        
        int[,] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        
        while (pq.Count > 0) {
            var (time, x, y) = pq.Dequeue();
            
            if (x == n - 1 && y == n - 1) {
                return time;
            }
            
            if (time > dist[x, y]) continue;
            
            for (int i = 0; i < 4; i++) {
                int nx = x + directions[i, 0];
                int ny = y + directions[i, 1];
                
                if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                    int newTime = Math.Max(time, grid[nx][ny]);
                    
                    if (newTime < dist[nx, ny]) {
                        dist[nx, ny] = newTime;
                        pq.Enqueue((newTime, nx, ny), newTime);
                    }
                }
            }
        }
        
        return -1;
    }
}

var swimInWater = function(grid) {
    const n = grid.length;
    const directions = [[0,1], [1,0], [0,-1], [-1,0]];
    
    let left = Math.max(grid[0][0], grid[n-1][n-1]);
    let right = n * n - 1;
    
    const canReach = (time) => {
        if (grid[0][0] > time || grid[n-1][n-1] > time) return false;
        
        const visited = Array(n).fill().map(() => Array(n).fill(false));
        const queue = [[0, 0]];
        visited[0][0] = true;
        
        while (queue.length > 0) {
            const [x, y] = queue.shift();
            
            if (x === n-1 && y === n-1) return true;
            
            for (const [dx, dy] of directions) {
                const nx = x + dx;
                const ny = y + dy;
                
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && 
                    !visited[nx][ny] && grid[nx][ny] <= time) {
                    visited[nx][ny] = true;
                    queue.push([nx, ny]);
                }
            }
        }
        
        return false;
    };
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (canReach(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
DijkstraO(n²log(n²))O(n²)
二分搜索 + BFSO(n²log(n²))O(n²)
并查集O(n²α(n²))O(n²)

其中 n 是网格的边长，α 是阿克曼函数的反函数。

相关题目