【Day 42 】2022-12-12 - 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] 内。

[yuxiangdev]

class Solution { public int swimInWater(int[][] grid) { int N = grid.length; int lo = 0, hi = N * N - 1; while (lo < hi) { int mi = lo + (hi - lo) / 2; boolean[][] visit = new boolean[N][N]; if (reachBottom(grid, mi, N, visit, 0, 0)) hi = mi; else lo = mi + 1; } return lo; }

private boolean reachBottom(int[][] grid, int t, int N, boolean[][] visit, int i, int j) {
    if (i < 0 || i >= N || j < 0 || j >= N || visit[i][j] || grid[i][j] > t) return false;
    visit[i][j] = true;
    if (i == N - 1 && j == N - 1) return true;
    else return reachBottom(grid, t, N, visit, i + 1, j) || reachBottom(grid, t, N, visit, i - 1, j) || reachBottom(grid, t, N, visit, i, j - 1) || reachBottom(grid, t, N, visit, i, j + 1);
}

}

[zjsuper]

class Solution: def swimInWater(self, grid: List[List[int]]) -> int:

search space

    l,r = 0,max([max(i) for i in grid])
    seen = set()
    def dfs(mid,l,r):

        if l<0 or l>len(grid)-1 or r < 0 or  r>len(grid)-1:
            return False
        if grid[l][r] >mid:
            return False
        if (l,r) in seen:
            return False
        if (l,r) == (len(grid)-1,len(grid)-1):

            return True
        seen.add((l,r))
        ans = dfs(mid,l,r+1) or dfs(mid,l,r-1) or dfs(mid,l+1,r) or dfs(mid,l-1,r) 
        return ans

    while l<=r:
        mid = (l+r)//2
        if dfs(mid,0,0):
            r = mid-1
        else:
            l = mid+1
        seen = set()
    return l

[Ryanbaiyansong]

class UF:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1 for i in range(n)]

    def union(self, x, y):
        fx = self.find(x)
        fy = self.find(y)
        if fx == fy:
            return
        if self.size[fx] < self.size[fy]:
            fx, fy = fy, fx
        self.size[fx] += self.size[fy]
        self.parent[fy] = fx

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def isConnected(self, x, y):
        return self.find(x)==self.find(y)

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        /////# time = 16 的时候, 首尾连通了
        edges = []
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                edges.append((x, i, j))
        uf = UF(m*n)
        edges.sort(key=lambda it:it[0])
        ////print(edges)
        ///# 双指针
        t = 0
        while not uf.isConnected(0, m*n-1):
            t+=1
            while j < m*n and edges[j][0] <= t:
                uf.union(0, edges[j][1]*n+edges[j][2])
                j+=1

        return t

[Ryanbaiyansong]

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dirs = [(-1,0), (1,0), (0,-1), (0,1)]
        def check(time):
            '''
            under time, if we can visit the (n-1,n-1)
            '''
            vis = set([(0,0),])
            q = deque([(0,0),])
            while q:
                x,y = q.popleft()
                if (x,y) == (m-1, n-1):
                    return True
                for dx, dy in dirs:
                    nx,ny = x+dx, y+dy
                    if 0<=nx<m and 0<=ny<n and max(grid[x][y], grid[nx][ny]) <= time and (nx, ny) not in vis:
                        q.append((nx,ny))
                        vis.add((nx,ny)) 
            return False

        l,r = 0, m*n-1
        while l < r:
            mid = (l+r) // 2
            if check(mid):
                r = mid
            else:
                l = mid+1
        return r

[Ryanbaiyansong]

··· class Solution: def swimInWater(self, grid: List[List[int]]) -> int: minHeap = [(grid[0][0], 0,0)] vis = {} m, n= len(grid), len(grid[0]) dirs = [(-1,0), (1,0), (0,-1),(0,1)] while minHeap: val, x, y = heappop(minHeap) if (x, y) in vis: continue vis[(x,y)] = val if (x,y) == (n-1, n-1): return val for dx, dy in dirs: nx, ny = x+dx, y+dy if 0<=nx<m and 0<=ny<n and (nx,ny) not in vis: heappush(minHeap, (max(val, grid[nx][ny]), nx, ny)) ···

[arinzz]

class Solution { public: int swimInWater(vector<vector>& grid) { int m=grid.size(); int n=grid[0].size(); UnionFind uf(mn); vector<tuple<int,int,int>>edge; for(int i=0;i<m;i++) for(int j=0;j<n;j++){ int id=in+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;

}

};

[testplm]

class Solution(object):
    def swimInWater(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        # 其实就是从矩阵的左上角到右上角，然后想办法走最短路径
        m = len(grid)
        l,r = 2*m-2,m*m

        def search(i,j):
            if ele[i][j]:
                return False
            ele[i][j] = 1
            if grid[i][j]<=ans:
                if i==j==m-1:
                    return True
                return any([search(a,b) for a,b in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)] if 0<=a<m and 0<=b<m])

        for ans in range(max(l,grid[-1][-1]),r):
            ele = [[0]*m for _ in range(m)]
            if search(0,0):
                return ans

• Time:O(NlogM)
• Space:O(N)

[wtdcai]

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

[ringo1597]

代码

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class Solution {

    // Dijkstra 算法（应用前提：没有负权边，找单源最短路径）

    public int swimInWater(int[][] grid) {
        int n = grid.length;

        Queue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(o -> grid[o[0]][o[1]]));
        minHeap.offer(new int[]{0, 0});

        boolean[][] visited = new boolean[n][n];
        // distTo[i][j] 表示：到顶点 [i, j] 须要等待的最少的时间
        int[][] distTo = new int[n][n];
        for (int[] row : distTo) {
            Arrays.fill(row, n * n);
        }
        distTo[0][0] = grid[0][0];

        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while (!minHeap.isEmpty()) {
            // 找最短的边
            int[] front = minHeap.poll();
            int currentX = front[0];
            int currentY = front[1];
            if (visited[currentX][currentY]) {
                continue;

[bookyue]

code

1. binary search + dfs
2. dijkstra

class Solution {
    private static final int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int left = grid[0][0];
        int right = n * n - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (feasible(grid, 0, 0, new boolean[n][n], mid))
                right = mid;
            else
                left = mid + 1;
        }

        return left;
    }

    private boolean feasible(int[][] grid, int x, int y, boolean[][] visited, int depth) {
        visited[x][y] = true;
        for (var dir : dirs) {
            int row = x + dir[0];
            int col = y + dir[1];
            if (row >= 0 && row < grid.length && col >= 0 && col < grid.length
                && !visited[row][col] && grid[row][col] <= depth) {
                if (row == grid.length - 1 && col == grid.length - 1) return true;

                if (feasible(grid, row, col, visited, depth)) return true;
            }
        }

        return false;
    }
}

class Solution {
    private static final int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int swimInWater(int[][] grid) {
        int n = grid.length;

        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(i -> grid[i[0]][i[1]]));
        minHeap.offer(new int[] {0, 0});

        boolean[][] visited = new boolean[n][n];
        int[][] dist = new int[n][n];
        for (int[] row : dist)
            Arrays.fill(row, n * n);

        dist[0][0] = grid[0][0];

        while (!minHeap.isEmpty()) {
            int[] v = minHeap.poll();
            int x = v[0];
            int y = v[1];
            if (visited[x][y]) continue;

            visited[x][y] = true;
            if (x == n - 1 && y == n - 1) return dist[n - 1][n - 1];

            for (int[] dir : dirs) {
                int row = x + dir[0];
                int col = y + dir[1];
                if (row >= 0 && row < n && col >= 0 && col < n
                    && Math.max(dist[x][y], grid[row][col]) < dist[row][col]) {
                    dist[row][col] = Math.max(dist[x][y], grid[row][col]);
                    minHeap.offer(new int[] {row, col});
                }
            }
        }

        return -1;
    }
}

[bwspsu]

(Referring to the solution)

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        l, r = 0, max([max(vec) for vec in grid])
        seen = set()

        def test(mid, x, y):
            if x > len(grid) - 1 or x < 0 or y > len(grid[0]) - 1 or y < 0:
                return False
            if grid[x][y] > mid:
                return False
            if (x, y) == (len(grid) - 1, len(grid[0]) - 1):
                return True
            if (x, y) in seen:
                return False
            seen.add((x, y))
            ans = test(mid, x + 1, y) or test(mid, x - 1,
                                              y) or test(mid, x, y + 1) or test(mid, x, y - 1)
            return ans
        while l <= r:
            mid = (l + r) // 2
            if test(mid, 0, 0):
                r = mid - 1
            else:
                l = mid + 1
            seen = set()
        return l

[mayloveless]

思路

根据可能的值做二分查找，每个遍历到的值需满足：从左上角开始在不高于这个值的情况下，遍历到grid的右下角。

代码

var swimInWater = function(grid) {
    const nodesCount = grid.length*grid.length;
    let low = 0;
    let high = nodesCount - 1;
     while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        if (findWhetherExistsPath(grid, mid)) {// 如果有这样一条路径的话
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return low;
};

var findWhetherExistsPath = function(graph, mid) {
    if (graph[0][0] > mid) return false;// 一开始就大于，则不必遍历

    const n = graph.length;
    const visited = Array(n).fill().map(() => Array(n).fill(false))
    const dfs = (i, j) => {
        visited[i][j] = true
        let directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        for (let k = 0; k < 4; ++k) {
            let newi = i + directions[k][0]
            let newj = j + directions[k][1]
            if (newi >= 0 && newi < n && newj >= 0 && newj < n
                && visited[newi][newj] == false && graph[newi][newj] <= mid) {
                dfs(newi, newj)
            }
        }
    }
    dfs(0,0)
    return visited[n-1][n-1]
};

复杂度

时间：O(n^2logn) 二分logn，dfs：n^2 空间：O（n^2） visted

[Abby-xu]

思路

抄答案 / Dijkstra

代码

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        nums_rows = num_cols = len(grid)

        def get_neighbors(row, col):
            delta_rows = [-1, 0, 1, 0]
            delta_cols = [0, 1, 0, -1]
            neighbors = []
            for i in range(len(delta_rows)):
                new_row = row + delta_rows[i]
                new_col = col + delta_cols[i]
                if new_row < 0 or new_row >= nums_rows or new_col < 0 or new_col >= num_cols:
                    continue
                neighbors.append((new_row, new_col))

            return neighbors

        min_heap = [(grid[0][0], (0, 0))]
        heapq.heapify(min_heap)
        curr_max = float('-inf')
        visited = set()
        while min_heap:
            val, (row, col) = heapq.heappop(min_heap)
            if (row, col) in visited:
                continue
            visited.add((row, col))

            if (row, col) == (nums_rows - 1, num_cols - 1):
                return max(curr_max, grid[nums_rows - 1][num_cols - 1])

            curr_max = max(curr_max, val)
            for neighbor in get_neighbors(row, col):
                nr, nc = neighbor
                heapq.heappush(min_heap, (grid[nr][nc], (nr, nc)))

        return -1  

复杂度

。。。

[chenming-cao]

解题思路

能力二分+DFS。解空间为[0, max]，按照题目max = n * n - 1。每次二分，判断从起点(0, 0)能否有一条路径不经过大于mid值的点到达终点(n, n)，可以通过DFS来判断。最后返回最左边满足条件的点即为最终结果。

代码

class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int l = 0, r = n * n - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            int[][] visited = new int[n][n];
            if (dfs(grid, 0, 0, visited, mid)) r = mid - 1;
            else l = mid + 1;
        }
        return l;
    }

    private boolean dfs(int[][] grid, int row, int col, int[][] visited, int mid) {
        int n = grid.length;
        if (row < 0 || row > n - 1 || col < 0 || col > n - 1) return false;
        else if (grid[row][col] > mid || visited[row][col] == 1) return false;

        if (row == n - 1 && col == n - 1) return true;
        visited[row][col] = 1;
        return dfs(grid, row + 1, col, visited, mid) || dfs(grid, row - 1, col, visited, mid) || dfs(grid, row, col + 1, visited, mid) || dfs(grid, row, col - 1, visited, mid);
    }
}

复杂度分析

• 时间复杂度：O(NlogMax)，N为grid的大小，Max为grid中最大值
• 空间复杂度：O(N)，N为grid的大小

[Alyenor]

function swimInWater(grid: number[][]): number {
    let g = grid,n=grid.length,st=[]
    const dx = [-1, 0, 1, 0]
    const dy = [0, 1, 0, -1]

    const dfs=(x,y,mid)=>{
        if(x===n-1 && y===n-1) return true
        st[x][y]=true
        for(let i=0;i<4;i++){
            let a=dx[i]+x,b=dy[i]+y
            if(a>=0&&a<n&&b>=0&&b<n&&g[a][b]<=mid&&!st[a][b]){
                if(dfs(a,b,mid)) return true
            }
        }
        return false
    }

    const check=(mid:number)=>{
        if(g[0][0]>mid) return false
        st=Array.from(new Array(n)).map(() => new Array(n).fill(false))
        return dfs(0,0,mid)
    }

    let l=0,r=n*n-1
    while(l<r){
        let mid=l+r>>1
        console.log(mid,check(mid))
        if(check(mid)) r=mid
        else l=mid+1
    }
    return l
};

[Elsa-zhang]

''' 778. 水位上升的泳池中游泳
    在一个 N x N 的坐标方格 grid 中,每一个方格的值 grid[i][j] 表示在位置 (i,j) 的平台高度。

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

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

    # 思路
    我们执行广度优先搜索，并只去访问那些高度不超过 threshold 的方格。如果能访问到终点，说明存在这样一种路径。
    如果能在 threshold 时间内从起点到达终点，则一定也能在 threshold+1 的时间内从起点到达终点。
    因此，我们可以通过二分查找的方式，寻找最小可能的 threshold

'''

class Solution:
    def test(self, mid, x, y, grid, record):
        if x>len(grid)-1 or y>len(grid[0])-1:
            return False
        if x<0 or y<0:
            return False
        if grid[x][y] > mid:
            return False
        if (x, y) == (len(grid)-1, len(grid[0])-1):
            return True
        if (x, y) in record:
            return False

        record.add((x, y))

        ans = self.test(mid, x+1, y, grid, record) or self.test(mid, x-1, y, grid, record) \
            or self.test(mid, x, y+1, grid, record) or self.test(mid, x, y-1, grid, record)

        return ans

    def swimInWater(self, grid: list[list[int]]):
        l = 0
        r = max([max(depth) for depth in grid]) #最大水位

        record = set()
        while l<=r:
            mid = (l+r)//2
            if self.test(mid, 0, 0, grid, record):
                r = mid-1
            else:
                l = mid+1
            record = set()

        return l

[zywang0]

class Solution {
    private static final int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int swimInWater(int[][] grid) {
        int n = grid.length;

        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(i -> grid[i[0]][i[1]]));
        minHeap.offer(new int[] {0, 0});

        boolean[][] visited = new boolean[n][n];
        int[][] dist = new int[n][n];
        for (int[] row : dist)
            Arrays.fill(row, n * n);

        dist[0][0] = grid[0][0];

        while (!minHeap.isEmpty()) {
            int[] v = minHeap.poll();
            int x = v[0];
            int y = v[1];
            if (visited[x][y]) continue;

            visited[x][y] = true;
            if (x == n - 1 && y == n - 1) return dist[n - 1][n - 1];

            for (int[] dir : dirs) {
                int row = x + dir[0];
                int col = y + dir[1];
                if (row >= 0 && row < n && col >= 0 && col < n
                    && Math.max(dist[x][y], grid[row][col]) < dist[row][col]) {
                    dist[row][col] = Math.max(dist[x][y], grid[row][col]);
                    minHeap.offer(new int[] {row, col});
                }
            }
        }

        return -1;
    }
}

[tiandao043]

思路

第一反应并查集，想起来二分专题，那应该就是二分值，dfs看到没到。

代码

class Solution {
public:
    bool dfs(int value, int x,int y,vector<vector<int>>& visited, vector<vector<int>>& grid){
        if(x > grid.size() - 1 || x < 0 || y > grid[0].size() - 1 || y < 0) return false;
        if(grid[x][y]>value)return false;
        if (x == grid.size() - 1 && y == grid[0].size() - 1) return true;
        if(visited[x][y]==1)return false;
        visited[x][y]=1;
        if(dfs(value,x+1,y,visited,grid)||dfs(value,x-1,y,visited,grid)||dfs(value,x,y+1,visited,grid)||dfs(value,x,y-1,visited,grid))return true;
        else return false;

    }
    int swimInWater(vector<vector<int>>& grid) {
        int l=0,r=-1;
        int row=grid.size();
        int col=grid[0].size();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < grid[i].size(); j++) r = max(r, grid[i][j]);
        }

        while(l<=r){
            vector<vector<int>> visited(row,vector<int>(col, 0));
            int mid=(l+r)/2;
            if(dfs(mid,0,0,visited,grid)){
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        return l;
    }
};

O(n^2log⁡n) O(n^2)

[snmyj]

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        UnionFind unionFind(n*n);
        vector<int> height(n*n);
        for(int loc = 0; loc < n*n; loc++) {
            height[grid[loc / n][loc % n]] = loc;
        }

        for(int ans = 0; ans < n*n; ans++) {
            int location = height[ans];
            int i = location / n;
            int j = location % n;
            if(i+1 < n and grid[i+1][j] <= ans) {
                unionFind.merge(location, (i+1)*n + j);
            }
            if(i-1 >= 0 and grid[i-1][j] <= ans) {
                unionFind.merge(location, (i-1)*n + j);
            }
            if(j+1 < n and grid[i][j+1] <= ans) {
                unionFind.merge(location, i*n + j+1);
            }
            if(j-1 >= 0 and grid[i][j-1] <= ans) {
                unionFind.merge(location, i*n + j-1);
            }

            if(unionFind.find(0) == unionFind.find(n*n-1)) {
                return ans;
            }
        }
        return n*n-1;
    }

};

[A-pricity]

/**
 * @param {number[][]} grid
 * @return {number}
 */
var swimInWater = function(grid) {
    let ARR = [[0,1],[0,-1],[1,0],[-1,0]];
    //记录所有已经访问过的点
    let dp = new Array(grid.length).fill(0).map(i=>new Array(grid[0].length).fill(0));
    let result = 0;
    let stack=[[0,0]];

    while(stack.length>0){
        let [row,col] = stack.shift();
        //用以记录当前已经保存的所有能走的点
        result = Math.max(result,grid[row][col]);

        if(row===grid.length-1 && col===grid[0].length-1){
            //达到终点结束遍历
            break;
        }
        for(let [dr,dc] of ARR){
            let [nr,nc] = [dr+row,dc+col];
            if(nr<grid.length && nr>=0 && nc<grid[0].length && nc>=0 && !dp[nr][nc]){
                dp[nr][nc]=1
                //此处若使用二分查找插入还能对时间进行优化
                stack.push([nr,nc,grid[nr][nc]])
            }
        }
        //排序还能使用二分插入法进行优化
        stack.sort((a,b)=>a[2]-b[2])
    }
    return result;
};

[want2333]

【Day 42】778. 水位上升的泳池中游泳

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;

    }
};

[syh-coder]

class Solution { public: bool dfs(int mid, int x, int y, set<pair<int, int>>& visited, vector<vector>& grid) { if (x > grid.size() - 1 || x < 0 || y > grid[0].size() - 1 || y < 0) return false; if (grid[x][y] > mid) return false; if (x == grid.size() - 1 && y == grid[0].size() - 1) return true; if (visited.count({x, y})) return false; visited.insert({x, y}); bool res = 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); return res; }

int swimInWater(vector<vector<int>>& grid) {
    int l = 0;
    int r = INT_MIN;
    for (int i = 0; i < grid.size(); i++) {
        for (int j = 0; j < grid[i].size(); j++) r = max(r, grid[i][j]);
    }
    set<pair<int, int>> visited;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (dfs(mid, 0, 0, visited, grid)) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
        visited.clear();
    }
    return l;
}

};

[klspta]

思路

答案范围在0到n * n - 1 范围内，并且整个区间具有二段性，可以用二分；然后用 dfs 检查二分的结果是否正确即可。

class Solution {
    public int swimInWater(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                min = Math.min(min, grid[i][j]);
                max = Math.max(max, grid[i][j]);
            }
        }
        int left = min;
        int right = max;
        int res = 0;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(check(grid, mid)){
                res = mid;
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return res;
    }

    private boolean check(int[][] grid, int mid){
        if(grid[0][0] > mid){
            return false;
        }
        boolean[][] map = new boolean[grid.length][grid[0].length];
        return dfs(grid, mid, map, 0, 0);
    }

    int[] dx = new int[]{0, 1, 0, -1};
    int[] dy = new int[]{1, 0, -1, 0};

    private boolean dfs(int[][] grid, int mid, boolean[][] map, int x, int y){
        map[x][y] = true;
        if(x == grid.length - 1 && y == grid[0].length - 1){
            return true;
        }
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < grid.length && nx >= 0 && ny < grid[0].length && ny >= 0 && grid[nx][ny] <= mid && !map[nx][ny]){
                if(dfs(grid, mid, map, nx, ny)){
                    return true;
                }
            }
        }
        return false;
    }
}

[syh-coder]

你好，我是宋宇恒，我已收到你的邮件，我会尽快查阅，谢谢

[RestlessBreeze]

struct Entry {
    int i;
    int j;
    int val;
    bool operator<(const Entry& other) const {
        return this->val > other.val;
    }
    Entry(int ii, int jj, int val): i(ii), j(jj), val(val) {}
};

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        priority_queue<Entry, vector<Entry>, function<bool(const Entry& x, const Entry& other)>> pq(&Entry::operator<);
        vector<vector<int>> visited(n, vector<int>(n, 0));

        pq.push(Entry(0, 0, grid[0][0]));
        int ret = 0;
        vector<pair<int, int>> directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while (!pq.empty()) {
            Entry x = pq.top();
            pq.pop();
            if (visited[x.i][x.j] == 1) {
                continue;
            }

            visited[x.i][x.j] = 1;
            ret = max(ret, grid[x.i][x.j]);
            if (x.i == n - 1 && x.j == n - 1) {
                break;
            }

            for (const auto [di, dj]: directions) {
                int ni = x.i + di, nj = x.j + dj;
                if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
                    if (visited[ni][nj] == 0) {
                        pq.push(Entry(ni, nj, grid[ni][nj]));
                    }
                }
            }
        }
        return ret;
    }
};

[BruceZhang-utf-8]

代码

• 语言支持：Java

Java Code:

class Solution {
    private int n;
    private int[][] grid;
    private int[] dx = {-1, 1, 0, 0};
    private int[] dy = {0, 0, -1, 1};

    public int swimInWater(int[][] grid) {
        n = grid.length;
        this.grid = grid;
        int left = Math.max(grid[0][0], grid[n - 1][n - 1]);
        int right = n * n - 1;

        while(left <= right){
            int mid = (left + right) / 2;
            if(dfs(mid, 0, 0, new boolean[n][n])){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean dfs(int t, int x, int y, boolean[][] visited){
        if(x == n - 1 & y == n - 1){
            return true;
        }
        visited[x][y] = true;
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny] && grid[nx][ny] <= t){
                if(dfs(t, nx, ny, visited)){
                    return true;
                }
            }
        }
        return false;

    }
}

[paopaohua]

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;

    }
};

[954545647]

var swimInWater = function(grid) { let ARR = [[0,1],[0,-1],[1,0],[-1,0]]; //记录所有已经访问过的点 let dp = new Array(grid.length).fill(0).map(i=>new Array(grid[0].length).fill(0)); let result = 0; let stack=[[0,0]];

while(stack.length>0){
    let [row,col] = stack.shift();
    //用以记录当前已经保存的所有能走的点
    result = Math.max(result,grid[row][col]);

    if(row===grid.length-1 && col===grid[0].length-1){
        //达到终点结束遍历
        break;
    }
    for(let [dr,dc] of ARR){
        let [nr,nc] = [dr+row,dc+col];
        if(nr<grid.length && nr>=0 && nc<grid[0].length && nc>=0 && !dp[nr][nc]){
            dp[nr][nc]=1
            //此处若使用二分查找插入还能对时间进行优化
            stack.push([nr,nc,grid[nr][nc]])
        }
    }
    //排序还能使用二分插入法进行优化
    stack.sort((a,b)=>a[2]-b[2])
}
return result;

};

[Alexno1no2]

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

[Jetery]

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

思路

二分 + dfs

代码 (cpp)

class Solution {
public:
    typedef pair<int, int> PII;
    int dirs[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        int l = 0, r = n * n;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (dfs(grid, mid)) r = mid;
            else l = mid + 1;
        }
        return l;
    }

    bool dfs(vector<vector<int>> &grid, int time) {
        if (time < grid[0][0]) return false;
        int n = grid.size();
        vector<vector<bool>> vis(n, vector<bool>(n, false));
        queue<PII> que;
        que.push({0, 0});
        vis[0][0] = true;
        while (!que.empty()) {
            auto [i, j] = que.front();
            que.pop();
            for (auto dir : dirs) {
                int x = i + dir[0];
                int y = j + dir[1];
                if (x < 0 || y < 0 || x >= n || y >= n) continue;
                if (grid[x][y] > time || vis[x][y] == true) continue;
                vis[x][y] = true;
                que.push({x, y});
            }
        }
        return vis[n - 1][n - 1];
    }
};

复杂度分析

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

[FlipN9]

/**
    Approach 1: 二分查找 最短的等待时间, 看能不能找到一条路径
    TC: O(N ^ 2 logN)   SC: O(N^2)
*/
class Solution1 {
    public static final int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    int N;
    int[][] grid;

    public int swimInWater(int[][] grid) {
        this.N = grid.length;
        this.grid = grid;

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

    private boolean dfs(int x, int y, boolean[][] visited, int threshold) {
        if (x == N - 1 && y == N - 1) 
            return true;
        visited[x][y] = true;
        for (int[] dir : dirs) {
            int i = x + dir[0], j = y + dir[1];
            if (isValid(i, j) && !visited[i][j] && grid[i][j] <= threshold) 
                if (dfs(i, j, visited, threshold))
                    return true;
        }
        return false;
    }

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

[neado]

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        l, r = 0, max([max(vec) for vec in grid])
        seen = set()

        def test(mid, x, y):
            if x > len(grid) - 1 or x < 0 or y > len(grid[0]) - 1 or y < 0:
                return False
            if grid[x][y] > mid:
                return False
            if (x, y) == (len(grid) - 1, len(grid[0]) - 1):
                return True
            if (x, y) in seen:
                return False
            seen.add((x, y))
            ans = test(mid, x + 1, y) or test(mid, x - 1,
                                              y) or test(mid, x, y + 1) or test(mid, x, y - 1)
            return ans
        while l <= r:
            mid = (l + r) // 2
            if test(mid, 0, 0):
                r = mid - 1
            else:
                l = mid + 1
            seen = set()
        return l

[whoam-challenge]

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