【Day 42 】2023-12-27 - 778. 水位上升的泳池中游泳

[azl397985856]

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

入选理由

暂无

题目地址

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

前置知识

暂无

题目描述

在一个 N x N 的坐标方格  grid 中，每一个方格的值 grid[i][j] 表示在位置 (i,j) 的平台高度。

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

你从坐标方格的左上平台 (0，0) 出发。最少耗时多久你才能到达坐标方格的右下平台  (N-1, N-1)？

示例 1:

输入: [[0,2],[1,3]] 输出: 3 解释: 时间为 0 时，你位于坐标方格的位置为 (0, 0)。 此时你不能游向任意方向，因为四个相邻方向平台的高度都大于当前时间为 0 时的水位。

等时间到达 3 时，你才可以游向平台 (1, 1). 因为此时的水位是 3，坐标方格中的平台没有比水位 3 更高的，所以你可以游向坐标方格中的任意位置 示例 2:

输入: [[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 解释: 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，此时才能保证平台 (0, 0) 和 (4, 4) 是连通的

提示:

2 <= N <= 50. grid[i][j] 位于区间 [0, ..., N*N - 1] 内。

[Chloe-C11]

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        res = 0
        n = len(grid)
        heap = [(grid[0][0],0,0)]
        visited = set([(0,0)])

        while heap:
            height,x,y = heapq.heappop(heap)
            res = max(res,height)
            if x == n-1 and y == n-1:
                return res

            for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
                new_x,new_y = x + dx,y + dy
                if 0 <= new_x < n and 0 <= new_y < n and (new_x,new_y) not in visited:
                    visited.add((new_x,new_y))
                    heapq.heappush(heap,(grid[new_x][new_y],new_x,new_y))

        return -1

[snmyj]

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int m=grid.size();
        int n=grid[0].size();
        UnionFind uf(m*n);
        vector<tuple<int,int,int>>edge;
        for(int i=0;i<m;i++)
        for(int j=0;j<n;j++){
            int id=i*n+j;
            if(i>0)edge.emplace_back(max(grid[i][j],grid[i-1][j]),id,id-m);
            if(j>0)edge.emplace_back(max(grid[i][j],grid[i][j-1]),id,id-1);
        }
        sort(edge.begin(),edge.end());
        int res=0;
        for(auto&[v,x,y]:edge){
            uf.merge(x,y);
            if(uf.connected(0,n*n-1)){
                res=v;
                break;
            }
        }
        return res;

    }
};

[Junru281]

Leetcode Dec 26

778. Swim in Rising Water

确实很难想到是二分法. 根据题解, 因为是有限解空间, 所以可以二分法. 首先就要先找到解空间,上界和下界.然后运用dfs来判断

class Solution {
    public boolean dfs(int mid, int x, int y, boolean[][] visited, int[][] grid){
        if (x > grid.length - 1 || x < 0 || y > grid[0].length - 1 || y < 0) return false;
        if (grid[x][y] > mid) return false;
        if(x == grid.length - 1&& y == grid[0].length - 1) return true;
        if (visited[x][y]) return false;
        visited[x][y] = true;
        return dfs(mid, x + 1, y, visited, grid) || dfs(mid, x - 1, y, visited, grid) || dfs(mid, x, y + 1, visited, grid) || dfs(mid, x, y - 1, visited, grid);
    }
    public int swimInWater(int[][] grid) {
        int l = 0;
        int r = Integer.MAX_VALUE;
        //先找出解空间
        for(int i = 0; i< grid.length; i++){
            for(int j = 0; j<grid[0].length; j++){
                if(r<grid[i][j]){
                    r = grid[i][j];
                }
            }
        }
        // 二分法
        while (l <= r) {
            boolean[][] visited = new boolean[grid.length][grid[0].length];
            int mid = l + (r - l) / 2;
            if (dfs(mid, 0, 0, visited, grid)) {
                r = mid - 1; // 成为一个备胎, 但不一定是最小的
            } else {
                l = mid + 1; // head towards 最小的选项
            }
        }
        return l;
    }
}

[Danielyan86]

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        res = 0
        n = len(grid)
        heap = [(grid[0][0],0,0)]
        visited = set([(0,0)])

        while heap:
            height,x,y = heapq.heappop(heap)
            res = max(res,height)
            if x == n-1 and y == n-1:
                return res

            for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
                new_x,new_y = x + dx,y + dy
                if 0 <= new_x < n and 0 <= new_y < n and (new_x,new_y) not in visited:
                    visited.add((new_x,new_y))
                    heapq.heappush(heap,(grid[new_x][new_y],new_x,new_y))

        return -1

[larscheng]

思路

二分查找+深度优先遍历

在方格数值区间[0,N*N-1]中找一个数作为等待时间，使其满足：存在从左上角到右下角的路径，且该数要最小

• 通过二分查找在区间内找符合条件的数值
• 如果mid满足条件，继续检查小于mid的数，right=mid
• 如果mid不满足，说明等待时间太小，需要继续检查更大的数值，left=mid+1
• 通过深度优先遍历，从左上角（0,0）开始检查当前等待时间下，是否存在有效路径

代码

public class Solution {

    private int N;

    public  int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int swimInWater(int[][] grid) {
        this.N = grid.length;
        int left = 0;
        int right = N * N - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            boolean[][] visited = new boolean[N][N];
            if (grid[0][0] <= mid && dfs(grid, 0, 0, visited, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean dfs(int[][] grid, int x, int y, boolean[][] visited, int threshold) {
        visited[x][y] = true;
        for (int[] direction : DIRECTIONS) {
            int newX = x + direction[0];
            int newY = y + direction[1];
            if (inArea(newX, newY) && !visited[newX][newY] && grid[newX][newY] <= threshold) {
                if (newX == N - 1 && newY == N - 1) {
                    return true;
                }

                if (dfs(grid, newX, newY, visited, threshold)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean inArea(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N;
    }
}

复杂度

• 时间复杂度：O(n^2 logn)
• 空间复杂度：O(n^2)

[adfvcdxv]

var swimInWater = function (grid) { let n = grid.length let low = grid[0][0] let high = n * n while (low < high) { let mid = Math.floor((low + high) / 2) if (!isCanSwim(mid, grid)) { low = mid + 1 } else { high = mid } } return low }; const isCanSwim = (t, grid) => { let n = grid.length let vis = Array.from(Array(n), () => Array(n).fill(false)) let dfs = (row, col) => { if (row < 0 || col < 0 || row >= n || col >= n || vis[row][col] || grid[row][col] > t) { return false } if (row == n - 1 && col == n - 1) { return true } vis[row][col] = true return dfs(row + 1, col) || dfs(row - 1, col) || dfs(row, col + 1) || dfs(row, col - 1); } return dfs(0, 0) }