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

[yetfan]

思路 二分+dfs

代码

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        l = 0
        r = n * n - 1

        def dfs(grid, x, y, visited, time):
            visited[x][y] = 1
            for neib in [(0,1),(0,-1),(1,0),(-1,0)]:
                neibx = x + neib[0]
                neiby = y + neib[1]
                if neibx < 0 or neibx >= n or neiby < 0 or neiby >= n:
                    continue
                if visited[neibx][neiby] == 0 and grid[neibx][neiby]<=time:
                    if neibx == n - 1 and neiby == n - 1:
                        return True
                    if dfs(grid, neibx, neiby, visited, time):
                        return True
            return False

        while l < r:
            mid = (l + r) // 2
            visited = [[0 for _ in range(n)] for _ in range(n)]
            if grid[0][0] <= mid and dfs(grid, 0, 0, visited, mid):
                r = mid
            else:
                l = mid + 1
        return l

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

[Bochengwan]

思路

通过heap每次去到四周最小深度的格子，直到最后到达target。

代码

import heapq as hp
class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        N = len(grid)
        visited = set()
        visited.add((0,0))
        pq = [(grid[0][0],0,0)]
        res = 0
        while pq:
            d,r,c = hp.heappop(pq)
            res = max(res,d)
            if r==c==(N-1):
                return res

            for nr,nc in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
                if 0<=nr<N and 0<=nc<N and (nr,nc) not in visited:
                    hp.heappush(pq,(grid[nr][nc],nr,nc))
                    visited.add((nr,nc))

        return res

复杂度分析

• 时间复杂度：O(N2LOGN)，其中 N 为数组长度。
• 空间复杂度：O(N2)

[wangzehan123]

题目地址(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] 的排列。

前置知识

BFS

思路

用bfs搜索周围路径，用优先队列维护从而先向水位低的位置移动

关键点

代码

• 语言支持：Java

Java Code:

class Solution {
  class Cell {
    int x;
    int y;
    int t;

    public Cell(int x, int y, int t) {
      this.x = x;
      this.y = y;
      this.t = t;
    }
  }
  public int swimInWater(int[][] grid) {
    int[] direX = {1, -1, 0, 0};
    int[] direY = {0, 0, 1, -1};
    PriorityQueue<Cell> pq = new PriorityQueue<>(new Comparator<Cell>() {
      @Override
      public int compare(Cell o1, Cell o2) {
        return o1.t - o2.t;
      }
    });

    int m = grid.length;
    int n = grid[0].length;
    int res = 0;
    boolean[][] visited = new boolean[m][n];
    visited[0][0] = true;
    pq.add(new Cell(0,0,grid[0][0]));
    while (!pq.isEmpty()) {
      Cell current = pq.poll();
      res = Math.max(res, current.t);
      if (current.x == m - 1 && current.y == n - 1) {
        return res;
      }
      for (int i = 0; i < 4; i++) {
        int x = current.x + direX[i];
        int y = current.y + direY[i];
        if (x >= 0 && x < m && y >= 0 && y < n && !visited[x][y]) {
          visited[x][y] = true;
          pq.add(new Cell(x, y, grid[x][y]));
        }
      }
    }
    return -1;
  }
}

[zwx0641]

class Solution { public int swimInWater(int[][] grid) { Comparator<int[]> comparator = (a,b)->a[2]-b[2]; PriorityQueue<int[]> priorityQueue = new PriorityQueue(comparator); int row = grid.length; int column = grid[0].length; int[] visited = new int[rowcolumn]; priorityQueue.offer(new int[]{0,0,grid[0][0]}); visited[0]=1; int max =0; while(!priorityQueue.isEmpty()){ int[] item = priorityQueue.poll();//当前节点 max = Math.max(max,item[2]); if(item[0]==row-1&&item[1]==column-1){ return max; } int i=item[0],j=item[1]; if(i>0&&visited[(i-1)column+j]==0){//上 priorityQueue.offer(new int[]{i-1,j,grid[i-1][j]}); visited[(i-1)column+j]=1; } if(j>0&&visited[(icolumn+j-1)]==0){//左 priorityQueue.offer(new int[]{i,j-1,grid[i][j-1]}); visited[(icolumn+j-1)]=1; } if(i<row-1&&visited[(i+1)column+j]==0){//下 priorityQueue.offer(new int[]{i+1,j,grid[i+1][j]}); visited[(i+1)column+j]=1; } if(j<column-1&&visited[icolumn+j+1]==0){//右 priorityQueue.offer(new int[]{i,j+1,grid[i][j+1]}); visited[i*column+j+1]=1; }

    }
    return -1;
}

}

[ginnydyy]

Problem

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

Notes

• Binary Search and DFS
• Use binary search to find the left most value of t when can swim to the destination, which means for value t, there is a path from start point to the destination that all the values of the grids in the path are <= t
• The range for binary search is [0, n * n - 1], because in the problem requirement : 0 <= grid[i][j] < n^2
• Use DFS to check whether there is a path from start point to the destination for each t
• The start point of DFS is grid[0][0], check four directions and recursively call the DFS method for each neighbor
• Details:
  • need to create a int[][] directions to easily get the neighbors on four directions
  • need to maintain a boolean[][] visited to trim the possibilities
  • need to check whether the new grid is valid (in the grid[][] scope) before validating on other conditions to avoid out of bounds exception

Solution

class Solution {
    int[][] directions = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int start = 0;
        int end = n * n - 1;
        while(start + 1 < end){
            int mid = start + (end - start) / 2;
            boolean[][] visited = new boolean[n][n];
            if(mid > grid[0][0] && dfs(grid, 0, 0, visited, mid)){
                end = mid;
            }else{
                start = mid;
            }
        }
        boolean[][] visited = new boolean[n][n];
        return start >= grid[0][0] && dfs(grid, 0, 0, visited, start)? start: end;
    }

    private boolean dfs(int[][] grid, int i, int j, boolean[][] visited, int mid){
        visited[i][j] = true;
        for(int[] direction: directions){
            int newX = i + direction[0];
            int newY = j + direction[1];
            if(isValid(newX, newY, grid.length) && !visited[newX][newY] && grid[newX][newY] <= mid){
                if(newX == grid.length - 1 && newY == grid.length - 1){
                    return true;
                }

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

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

Complexity

• Time: O(logn^2 n^2) => O(2logn n^2) => O(n^2 logn). n is the one dimensional size of the grid. Binary search range is [0, n n -1], so costs O(logn^2). In each binary search, need to check all the grids in DFS method, there are n^2 grids, costs O(n^2).
• Space: O(n^2) for the boolean[][] visited array.

[zhiyuanpeng]

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

[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

[falconruo]

思路

二分法+DFS

复杂度

• 时间复杂度: O(N^2logN), 其中 N 是方格的边长
• 空间复杂度: O(N^2)

代码(C++)

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        n = grid.size();
        m = grid[0].size();

        int minDepth = INT_MAX, maxDepth = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                minDepth = min(minDepth, grid[i][j]);
                maxDepth = max(maxDepth, grid[i][j]);
            }
        }

        while (minDepth <= maxDepth) {
            int mid = minDepth + (maxDepth - minDepth)/2;
            set<pair<int, int>> visited;
            if (dfs(grid, mid, 0, 0, visited))
                maxDepth = mid - 1;
            else
                minDepth = mid + 1;
        }

        return minDepth;
    }
private:
    int n, m;
    int dfs(vector<vector<int>>& grid, int bar, int y, int x, set<pair<int, int>>& visited) {
        if (y < 0 || y >= n || x < 0 || x >= m || visited.count({y, x}) || grid[y][x] > bar) return 0;

        if (y == n - 1 && x == m - 1) return 1;

        visited.insert({y, x});

        vector<int> dirs = {0, 1, 0, -1, 0};
        for (int i = 0; i < 4; i++) {
            if (dfs(grid, bar, y + dirs[i], x + dirs[i + 1], visited))
                return 1;
        }

        return 0;
    }
};

[RocJeMaintiendrai]

class Solution {
    private int[] dx = {-1, 1, 0, 0};
    private int[] dy = {0, 0, -1, 1};
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int left = Math.max(grid[0][0], grid[n - 1][n - 1]);
        int right = n * n - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(dfs(mid, 0, 0, grid, new boolean[n][n], n)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean dfs(int t, int x, int y, int[][] grid, boolean[][] visited, int n) {
        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, grid, visited, n)) return true;
            }
        }
        return false;
    }
}

复杂度分析

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

[laofuWF]

# binary search + dfs
# from min_value to max_value, use binary search to find left most candidate that can finish the swimming

# time: (N + MlogN), N is the total number of elements in the grid, M is max value in the grid
# space: O(N)

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        dx = [0, -1, 1, 0]
        dy = [1, 0, 0, -1]

        rows = len(grid)
        cols = len(grid[0])
        visited = [[0 for i in range(cols)] for j in range(rows)]

        def can_finish(i, j, t):
            if i == rows - 1 and j == cols - 1 and grid[i][j] <= t:
                return True
            if grid[i][j] > t:
                return False

            visited[i][j] = 1
            for index in range(len(dx)):
                new_i = i + dx[index]
                new_j = j + dy[index]

                if new_i >= 0 and new_i <= rows - 1 and new_j >= 0 and new_j <= cols - 1 and visited[new_i][new_j] == 0:
                    if can_finish(new_i, new_j, t):
                        return True
            return False

        min_value = float('inf')
        max_value = float('-inf')
        for i in range(rows):
            for j in range(cols):
                min_value = min(min_value, grid[i][j])
                max_value = max(max_value, grid[i][j])

        # binary search: find left most element that can finish
        while min_value <= max_value:
            mid = min_value + (max_value - min_value) // 2

            visited = [[0 for i in range(cols)] for j in range(rows)]

            if can_finish(0, 0, mid):
                max_value = mid - 1
            else:
                min_value = mid + 1

        return min_value

[feifan-bai]

思路

1. DFS + 二分
2. 到一个绝对值差diff，使得小于等于diff的恰好有k个
3. 如果当前绝对差p小于k，舍弃当前一半解
4. 如果当前绝对差p大于k，舍弃当前一半解

代码

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

复杂度分析

• 时间复杂度：O(nlogm), n = grid, m = max(grid[i][j])
• 空间复杂度：O(n)

[Aobasyp]

思路 DFS + 二分

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;
}

};

时间复杂度：O(NlogM) 空间复杂度：O(N)

[Tesla-1i]

import heapq as hp
class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        N = len(grid)
        visited = set()
        visited.add((0,0))
        pq = [(grid[0][0],0,0)]
        res = 0
        while pq:
            d,r,c = hp.heappop(pq)
            res = max(res,d)
            if r==c==(N-1):
                return res

            for nr,nc in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
                if 0<=nr<N and 0<=nc<N and (nr,nc) not in visited:
                    hp.heappush(pq,(grid[nr][nc],nr,nc))
                    visited.add((nr,nc))

        return res

[LAGRANGIST]

代码

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        l = 0
        r = n * n - 1

        def dfs(grid, x, y, visited, time):
            visited[x][y] = 1
            for neib in [(0,1),(0,-1),(1,0),(-1,0)]:
                neibx = x + neib[0]
                neiby = y + neib[1]
                if neibx < 0 or neibx >= n or neiby < 0 or neiby >= n:
                    continue
                if visited[neibx][neiby] == 0 and grid[neibx][neiby]<=time:
                    if neibx == n - 1 and neiby == n - 1:
                        return True
                    if dfs(grid, neibx, neiby, visited, time):
                        return True
            return False

        while l < r:
            mid = (l + r) // 2
            visited = [[0 for _ in range(n)] for _ in range(n)]
            if grid[0][0] <= mid and dfs(grid, 0, 0, visited, mid):
                r = mid
            else:
                l = mid + 1
        return l

复杂度

时间 $O(n^2logn)$ 空间 $O(n^2)$

[yan0327]

思路： 小岛问题+猜值二分 【记住，go语言这里的话最好还是采用哈希表的性能会更好】 【此外，go语言的哈希表不支持切片，但是支持数组】

var hash map[[2]int]bool
func swimInWater(grid [][]int) int {
    hash = map[[2]int]bool{}
    n := len(grid)
    left,right :=0,n*n
    for left < right{
        mid := left + (right-left)>>1
        if !finish(grid,mid){
            left = mid+1
        }else{
            right = mid
        }
        hash = map[[2]int]bool{}
    }
    return left
}
func finish(grid [][]int, tar int) bool{
    n := len(grid)
    var dfs func(row int,col int,tar int) bool
    dfs = func(row int,col int,tar int) bool{
        if row<0||row>=n||col<0||col>=n||grid[row][col]>tar{
            return false
        }
        if row == n-1&&col == n-1{
            return true
        }
        if _,ok := hash[[2]int{row,col}];ok{
            return false
        }

        hash[[2]int{row,col}] = true
        flag := dfs(row+1,col,tar)||dfs(row-1,col,tar)||dfs(row,col+1,tar)||dfs(row,col-1,tar)
        return flag
    }
    return dfs(0,0,tar)
}

时间复杂度：O（N²logN） 空间复杂度：O（N²）

[JudyZhou95]

思路

Use binary search to search through [0, max elevation in grid], and each time test if the current time can make it to the right bottom corner. The trick part is how to check the curerent time is possible to make it. We use a helper function which uses DFS try to traverse from (0, 0) to (m-1, n-1) whenever the elevation of node in searching path is larger than time, we break this path.

代码

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

        m = len(grid)
        n = len(grid[0])

        def valid(time, x, y):
            if x < 0 or y < 0 or x >= m or y >= n:
                return False
            if (x, y) in visited:
                return False

            if grid[x][y] > time:
                return False

            return True

        def enough(time, x, y):

            if not valid(time, x, y):
                return False

            if x == m-1 and y == n-1:
                return True

            visited.add((x, y))
            for xx, yy in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:            
                if enough(time, xx, yy):
                    return True                    

            return False

        l = 0
        r = max([max(vec) for vec in grid])

        while l <= r:
            mid = l + (r-l)//2

            visited = set()
            if enough(mid, 0, 0):
                r = mid - 1
            else:
                l = mid + 1
        return l

复杂度

TC: O(NlogM) SC: O(N)

[xuhzyy]

 思路

二分+DFS

代码

class Solution(object):
    def swimInWater(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        n = len(grid)

        def test(value, x, y, seen):
            if grid[-1][-1] > value:
                return False
            if x < 0 or x > n - 1 or y < 0 or y > n - 1:
                return False
            if (x,y) in seen:
                return False
            if grid[x][y] > value:
                return False
            if x == n - 1 and y == n - 1:
                return True
            seen.append((x,y))
            return test(value, x-1, y, seen) or test(value, x+1, y, seen) or test(value, x, y-1, seen) or test (value, x, y+1, seen)

        left = 0
        right = 0
        for i in range(n):
            right = max(right, max(grid[i]))
        seen = []
        while(left <= right):
            mid = left + (right - left) // 2
            if test(mid, 0, 0, seen):
                right = mid - 1
            else:
                left = mid + 1
            seen = []
        return left  

复杂度

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

[hdyhdy]

思路： 二分法，DFS

//存放的是数组的长度以及数据
type Grid struct {
    G [][]int
    N int
}

func swimInWater(grid [][]int) int {
    //初始化结构体，数据就是坐标数组，长度就是坐标数组的总长度
    g := Grid{G: grid, N: len(grid)}

    //根据题解思路，该问题可以转换为找到一个0 - N * N -1之间的值，在该值之下能符合题解的要求到达终点，同时路径最短
    start := 0 
    end := g.N * g.N 

    //所以在该范围执行二分法，判断条件是，DFS是否能遍历到终点，如果不可以的话说明当前值太小了，要往大的找。
    for start <= end {
        mid := (end + start) / 2
        //每次遍历利用visit记录见过的坐标避免重复操作
        visit := make([]bool,g.N * g.N)
        if g.DFS(0, 0, mid, visit) {
            end = mid - 1 
        } else {
            start = mid + 1
        }
    }
    //如果最终结果小于初始位置的值，那么就返回初始位置的值
    if g.N > 0 && start < grid[0][0] {

        return grid[0][0]
    }

    return start
}

var dir = []int {0,1,0,-1,0}

func (g *Grid) DFS(x, y int, t int, visited []bool) bool {
    if x == g.N-1 && y == g.N-1 {
        return true
    }

    //向四个方向DFS
    for i := 0; i < 4; i++  {
        nx := x + dir[i]
        ny := y + dir[i+1]

        //对于无效的方向就跳过
        if nx < 0 || nx >= g.N || ny < 0 || ny >= g.N {
            continue
        }

        //循环过程中见过的也跳过
        if visited[nx*g.N+ny] {
            continue
        }

        //如果寻找的坐标的数据是小于目标值的，首先给这个坐标标记，然后再DFS看看它的附近有没有满足到达终点的可能性
        if g.G[nx][ny] <= t {
            visited[nx*g.N+ny] = true
            if g.DFS(nx, ny, t, visited) {
                return true
            }
        }
    }
    return false
}

时间复杂度：O（n2 logn） 空间复杂度：O（n2）

[Zhang6260]

JAVA版本

主要使用二分法+dfs，但是使用DFS会超时，就先这样 之后在尝试使用bfs吧

class Solution {
   //是否可以用二分的思想来解该题呢？？
   public int swimInWater(int[][] grid) {
       int min = 0;
       int max = grid.length*grid.length;
       while(min<max){
           int mid = (max - min)/2+ min;
           if(dfs(grid,mid,0,0)){
               max = mid;
           }else{
               min = mid + 1;
           }
       }
       return min;
   }
   //其中用index  来表示水位置
   public static boolean dfs(int[][]arr,int index,int i,int j){
       if(i<0||j<0||i>arr.length-1||j>arr.length-1||arr[i][j]>index){
           return false;
       }
       if(i==arr.length-1 && j==arr.length-1&&arr[i][j]<=index){
           return true;
       }
       int temp = arr[i][j];
       arr[i][j] = -1;  //访问过的进行标记

       boolean res = false;
       if(i-1>=0&&arr[i-1][j]<=index&&arr[i-1][j]!=-1){
           res |= dfs(arr,index,i-1,j);
       }
       if(j-1>=0&&arr[i][j-1]<=index&&arr[i][j-1]!=-1){
           res |= dfs(arr,index,i,j-1);
       }
       if(i+1<= arr.length-1&&arr[i+1][j]<=index&&arr[i+1][j]!=-1){
           res |= dfs(arr,index,i+1,j);
       }
       if(j+1<= arr.length-1&&arr[i][j+1]<=index&&arr[i][j+1]!=-1){
           res |= dfs(arr,index,i,j+1);
       }
       arr[i][j] = temp;
       return res;
   }
}

时间复杂度：O(nlogn)

空间复杂度：O(n）

[tongxw]

思路

类似200小岛问题 + 每个格子有权值grid[i][j]，求最短路径。套用DJ算法。

class Solution {
    public int swimInWater(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        PriorityQueue<int[]> q = new PriorityQueue<>((e1, e2) -> e1[2] - e2[2]); // {i, j, grid[i][j]}
        boolean[][] visited = new boolean[m][n];

        q.offer(new int[]{0, 0, grid[0][0]});
        visited[0][0] = true;

        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        int cost = 0;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            cost = Math.max(cost, cur[2]);
            if (cur[0] == m - 1 && cur[1] == n-1) {
                return cost;
            }

            for (int k=0; k<4; k++) {
                int row = cur[0] + dx[k];
                int col = cur[1] + dy[k];

                if (row < 0 || row >= m || col < 0 || col >= n || visited[row][col]) {
                    continue;
                }
                 visited[row][col] = true;
                q.offer(new int[]{row, col, grid[row][col]});
            }
        }

        return -1;
    }
}

TC: O(MN Log(min(M, N))) SC: O(MN)

[ZacheryCao]

Idea

Heap

Code

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        stack = [(grid[0][0], 0, 0)]
        ans = grid[0][0]
        seen = set()
        seen.add((0, 0))
        while stack:
            d, c, r = heapq.heappop(stack)
            ans = max(ans, d)
            if c == r == len(grid) - 1:
                return ans
            for cc, rr in {(r-1, c), (r+1,c),(r,c +1), (r,c-1)}:
                if 0<=cc<len(grid) and 0<=rr<len(grid) and (cc, rr) not in seen:
                    seen.add((cc, rr))
                    heapq.heappush(stack, (max(ans, grid[cc][rr]), cc, rr))
        return ans

Complexity:

Time: O(N^2 log N) Space: O(N^2)

[haixiaolu]

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        def dfs(t, x, y, visited):
            if x == y == n - 1:
                return True 
            visited[x][y] = True 
            for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                nx, ny = x + dx, y + dy 
                if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and grid[nx][ny] <= t:
                    if dfs(t, nx, ny, visited):
                        return True 
            return False 

        left = max(grid[0][0], grid[-1][-1])
        right = n * n - 1
        while left <= right:
            mid = (left + right) // 2
            visited = [[False] * n for _ in range(n)]
            if dfs(mid, 0, 0, visited):
                right = mid - 1
            else:
                left = mid + 1
        return left 

[ZJP1483469269]

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)   
        def dfs(x,y,water):
            if x < 0 or x >= n or y < 0 or y >= n:
                return False
            if grid[x][y] > water:
                return False
            if x == n-1 and y == n - 1:
                return True
            if vis[x][y] == 1:
                return False
            vis[x][y] = 1
            return dfs(x+1,y,water) or dfs(x,y+1,water) or dfs(x-1,y,water) or dfs(x,y-1,water)

        l , r = max(grid[0][0],grid[n-1][n-1]) , max(max(grid))

        while l < r:
            mid = (l + r) >> 1
            vis = [[0]*n for _ in range(n)]
            if dfs(0,0,mid) == True:
                r = mid
            else:
                l = mid + 1
        return l

[LannyX]

思路

二分 + BFS

代码

class Solution {
    int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int l = 0, r = n * n;
        while(l <= r){
            int mid = l + (r - l)/2;
            if(check(grid, mid)){
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }
    private boolean check(int[][] grid, int time){
        int n = grid.length;
        boolean[][] visited = new boolean[n][n];
        Deque<int[]> dq = new ArrayDeque<>();
        dq.addLast(new int[]{0,0});
        visited[0][0] = true;

        while(!dq.isEmpty()){
            int[] pos = dq.pollFirst();
            int x = pos[0], y = pos[1];
            if(x == n - 1 && y == n - 1) return true;

            for(int[] d : dir){
                int newX = x + d[0], newY = y + d[1];
                int[] to = new int[]{newX, newY};
                if(inArea(n, newX, newY) && !visited[newX][newY] && canMove(grid, pos, to, time)){
                    visited[newX][newY] = true;
                    dq.addLast(to);
                }
            }
        }
        return false;
    }
    private boolean inArea(int n, int x, int y){
        return x >= 0 && x < n && y >= 0 && y < n;
    }
    private boolean canMove(int[][] grid, int[] from, int[] to, int time){
        return time >= Math.max(grid[from[0]][from[1]], grid[to[0]][to[1]]);
    }
}

复杂度分析

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

[junbuer]

思路

• 二分法
• 确定时间的边界为[max(grid[0][0], grid[-1][-1]), max(max(grid))]，二分查找最小时间mid = (l + r) // 2
• 使用深度优先搜索遍历grid检查当前时间mid是否可以从(0 ,0)到(n - 1, n - 1)

  代码

class Solution(object):
    def swimInWater(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        n = len(grid) 
        def dfs(t, x, y):
            if x == n -1 and y == n- 1:
                return True
            if x < 0 or x >= n or y < 0 or y >= n:
                return False
            if grid[x][y] > t or visited[x][y]:
                return False
            visited[x][y] = 1
            return dfs(t, x + 1, y) or dfs(t, x - 1, y) or dfs(t, x, y + 1) or dfs(t, x, y - 1)

        l, r = max(grid[0][0], grid[-1][-1]), max(max(grid))
        while l < r:
            mid = l + (r - l) / 2
            visited = [[0]*n for _ in range(n)]
            if dfs(mid, 0, 0):
                r = mid
            else:
                l = mid + 1
        return l

复杂度分析

• 时间复杂度：$O(N^2logD)$，其中$D=l - r$
• 空间复杂度：$O(N^2)$

[1149004121]

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

思路

二分查找适合的高度，判断是否符合要求可以用dfs。

代码

var swimInWater = function(grid) {
    let min = 0, max = 0;
    const n = grid.length;
    for(let i = 0; i < n; i++){
        for(let j = 0; j < n; j++){
            max = Math.max(max, grid[i][j]);
        }
    };
    while(min < max){
        let mid = (min + max) >>> 1;
        if(isCapable(mid)) max = mid;
        else min = mid + 1;
    };
    return min;

    function isCapable(height){
        let visited = new Array(n).fill(false).map(() => new Array(n).fill(false));
        return dfs(0, 0, visited, height);
    };

    function dfs(i, j, visited, height){
        if(i < 0 || j < 0 || i >= n || j >= n || visited[i][j] === true || grid[i][j] > height) return false;
        if(i === n - 1 && j === n - 1) return true;
        let dire = [[1, 0], [-1, 0], [0, 1], [0, -1]];
        visited[i][j] = true;
        let res = dfs(i + dire[0][0], j + dire[0][1], visited, height) 
            || dfs(i + dire[1][0], j + dire[1][1], visited, height) 
            || dfs(i + dire[2][0], j + dire[2][1], visited, height) 
            || dfs(i + dire[3][0], j + dire[3][1], visited, height);
        return res;
    }
};

复杂度分析

• 时间复杂度：O(NlogM)，M为grid中最大值，N为grid中格子数。
• 空间复杂度：O(1)。

[Richard-LYF]

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

    def dfs(t,x,y,visited):
        if x==y==n-1:
            return True

        visited[x][y] = True
        for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and grid[nx][ny]<=t:
                if dfs(t,nx,ny,visited):
                    return True
        return False

    n = len(grid)

    left = max(grid[0][0], grid[-1][-1])
    right = n * n - 1

    while left <= right:
        mid = (left + right) // 2
        visited = [[False] * n for _ in range(n)]
        if dfs(mid, 0, 0, visited):
            right = mid - 1
        else:
            left = mid + 1
    return left

o n2logn on2

[KennethAlgol]

class Solution {
    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};
    public int swimInWater(int[][] grid) {
        boolean[][] visit = new boolean[grid.length][grid[0].length];
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);
        pq.offer(new int[]{0, 0, grid[0][0]});
        visit[0][0] = true;
        int res = 0;
        while (pq.size() > 0) {
            int[] a = pq.poll();
            int x = a[0];
            int y = a[1];
            res = Math.max(res, a[2]);
            if (x == grid.length - 1 && y == grid[0].length - 1) return res;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length && !visit[nx][ny]) {
                    pq.offer(new int[]{nx, ny, grid[nx][ny]});
                    visit[nx][ny] = true;
                }
            }
        }
        return 0;
    }
}

[zol013]

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

        def test(mid, x, y):
            if not(0 <= x < len(grid) and 0 <= y < len(grid[0])):
                return False
            if grid[x][y] > mid:
                return False
            if x == len(grid) -1 and y == 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
        '''

        N = len(grid)
        seen = {(0, 0)}
        pq = [(grid[0][0], 0 ,0)]
        ans = 0

        while pq:
            d, r, c = heappop(pq)
            ans = max(ans, d)
            if r == c == N - 1:
                return ans
            for cr, cc in ((r+1,c),(r-1,c),(r,c-1),(r,c+1)):
                if 0 <= cr < N and 0 <= cc < N and (cr, cc) not in seen:
                    heappush(pq, (grid[cr][cc], cr, cc))
                    seen.add((cr, cc))

[didiyang4759]

参考官方题解

public class Solution {

    private int N;

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

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

        int len = N * N;
        // 下标：方格的高度，值：对应在方格中的坐标
        int[] index = new int[len];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                index[grid[i][j]] = getIndex(i, j);
            }
        }

        UnionFind unionFind = new UnionFind(len);
        for (int i = 0; i < len; i++) {
            int x = index[i] / N;
            int y = index[i] % N;

            for (int[] direction : DIRECTIONS) {
                int newX = x + direction[0];
                int newY = y + direction[1];
                if (inArea(newX, newY) && grid[newX][newY] <= i) {
                    unionFind.union(index[i], getIndex(newX, newY));
                }

                if (unionFind.isConnected(0, len - 1)) {
                    return i;
                }
            }
        }
        return -1;
    }

    private int getIndex(int x, int y) {
        return x * N + y;
    }

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

    private class UnionFind {

        private int[] parent;

        public UnionFind(int n) {
            this.parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int root(int x) {
            while (x != parent[x]) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }

        public boolean isConnected(int x, int y) {
            return root(x) == root(y);
        }

        public void union(int p, int q) {
            if (isConnected(p, q)) {
                return;
            }
            parent[root(p)] = root(q);
        }
    }
}

[HondryTravis]

思路

优先队列

代码

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;

复杂度分析

时间复杂度 O(n^2)

空间复杂度 O(n^2)

[shamworld]

var swimInWater = function(grid) {
    const n = grid.length
    let lo = grid[0][0], hi = n * n - 1
    const dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]

    const canSwimToEnd = (max) => {
        const seen = new Set([0])
        const stack = [[0, 0]]
        while (stack.length) {
            const [x, y] = stack.pop()
            if (x === n - 1 && y === n - 1) {
                return true
            }
            dir.forEach(([dx, dy]) => {
                const nx = x + dx
                const ny = y + dy
                if (
                    0 <= nx && nx <= n - 1 &&
                    0 <= ny && ny <= n - 1 &&
                    !seen.has(nx * n + ny) &&
                    grid[nx][ny] <= max
                ) {
                    seen.add(nx * n + ny)
                    stack.push([nx, ny])
                }
            })
        }
        return false
    }

    while (lo < hi) {
        const m = Math.floor((lo + hi) / 2)
        if (canSwimToEnd(m)) {
            hi = m
        } else {
            lo = m + 1
        }
    }
    return lo
};

[MongoCZK]

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

[Myleswork]

　思路

二维DFS＋能力检测二分

以[０，maxdepth]作为初始区间，把mid送进DFS，以下是需要进行判断的情况：

1、游到泳池外面去了，return false

2、这块区域之前游到过了，return false

3、这块区域我还游不上去，return false

4、游到右下角了，return true！

然后DFS该点的上下左右四个区域

代码

class Solution {
public:
    bool DFS(vector<vector<int>>& grid,int mid,int x,int y,set<int>& visit){
        int N = grid.size();
        if(x<0 || x>N-1 || y<0 || y>N-1) return false; //到游泳池外面去了
        if(visit.find(grid[x][y]) != visit.end()) return false;  //已经访问过了
        if(grid[x][y] > mid) return false;             
        if(x == N-1 && y == N-1) return true;
        visit.emplace(grid[x][y]);
        bool res = DFS(grid,mid,x,y-1,visit) || DFS(grid,mid,x,y+1,visit) || DFS(grid,mid,x-1,y,visit) || DFS(grid,mid,x+1,y,visit);
        return res;
    }
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        int r = n*n-1;
        int l = 0;
        while(l<=r){
            int mid = (r-l)/2+l;
            set<int> visit;
            if(DFS(grid,mid,0,0,visit)) r = mid-1;
            else l = mid+1;
        }
        return l;
    }
};

复杂度分析

时间复杂度：O(nlogn)

空间复杂度：O(n)

[machuangmr]

代码

class Solution {
    int[][] dirs = new int[][]{{1,0}, {-1,0}, {0,1}, {0,-1}};
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int l = 0, r = n * n;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(grid, mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r;
    }
    boolean check(int[][] grid, int time) {
        int n = grid.length;
        boolean[][] visited = new boolean[n][n];
        Deque<int[]> queue = new ArrayDeque<>();
        queue.addLast(new int[]{0, 0});
        visited[0][0] = true;
        while (!queue.isEmpty()) {
            int[] pos = queue.pollFirst();
            int x = pos[0], y = pos[1];
            if (x == n - 1 && y == n - 1) return true;

            for (int[] dir : dirs) {
                int newX = x + dir[0], newY = y + dir[1];
                int[] to = new int[]{newX, newY};
                if (inArea(n, newX, newY) && !visited[newX][newY] && canMove(grid, pos, to, time)) {
                    visited[newX][newY] = true;
                    queue.addLast(to);
                }
            }
        }
        return false;
    }
    boolean inArea(int n, int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < n;
    }
    boolean canMove(int[][] grid, int[] from, int[] to, int time) {
        return time >= Math.max(grid[from[0]][from[1]], grid[to[0]][to[1]]);
    }
}

复杂度

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

[hx-code]

def test(x): pass while l <= r: mid = (l + r) // 2 if test(mid, 0, 0): r = mid - 1 else: l = mid + 1 return l

[guangsizhongbin]

class Solution { private int N;

public int swimInWater(int[][] grid) {
    N = grid.length;
    PriorityQueue<int[]> water = new PriorityQueue<int[]>((o1, o2) -> o1[2] - o2[2]);
    water.add(new int[] { 0, 0, grid[0][0] });
    int ans = 0;
    boolean[][] checked = new boolean[N][N];
    checked[0][0] = true;
    while (!water.isEmpty()) {
        int[] pos = water.poll();
        int x = pos[0];
        int y = pos[1];
        int higth = pos[2];
        if (higth > ans) {
            ans = higth;
        }
        if (x + 1 == N - 1 && y == N - 1) {// 为了少游一些比[N-1,N-1]低的点
            if ((higth = grid[x + 1][y]) > ans) {
                ans = higth;
            }
            break;
        }
        if (x == N - 1 && y + 1 == N - 1) {// 为了少游一些比[N-1,N-1]低的点
            if ((higth = grid[x][y + 1]) > ans) {
                ans = higth;
            }
            break;
        }
        this.swimTo(water, checked, x + 1, y, grid);
        this.swimTo(water, checked, x, y + 1, grid);
        this.swimTo(water, checked, x - 1, y, grid);
        this.swimTo(water, checked, x, y - 1, grid);
    }
    return ans;
}

private void swimTo(PriorityQueue<int[]> water, boolean[][] checked, int x, int y, int[][] grid) {
    if (x >= 0 && x < N && y >= 0 && y < N && !checked[x][y]) {
        checked[x][y] = true;
        water.add(new int[] { x, y, grid[x][y] });
    }
}

}

[alongchong]

class Solution {
    int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int l = 0, r = n * n;
        while(l <= r){
            int mid = l + (r - l)/2;
            if(check(grid, mid)){
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }
    private boolean check(int[][] grid, int time){
        int n = grid.length;
        boolean[][] visited = new boolean[n][n];
        Deque<int[]> dq = new ArrayDeque<>();
        dq.addLast(new int[]{0,0});
        visited[0][0] = true;

        while(!dq.isEmpty()){
            int[] pos = dq.pollFirst();
            int x = pos[0], y = pos[1];
            if(x == n - 1 && y == n - 1) return true;

            for(int[] d : dir){
                int newX = x + d[0], newY = y + d[1];
                int[] to = new int[]{newX, newY};
                if(inArea(n, newX, newY) && !visited[newX][newY] && canMove(grid, pos, to, time)){
                    visited[newX][newY] = true;
                    dq.addLast(to);
                }
            }
        }
        return false;
    }
    private boolean inArea(int n, int x, int y){
        return x >= 0 && x < n && y >= 0 && y < n;
    }
    private boolean canMove(int[][] grid, int[] from, int[] to, int time){
        return time >= Math.max(grid[from[0]][from[1]], grid[to[0]][to[1]]);
    }

[demo410]

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        #两点的边长为两点中最大的高度。建立一个边长集合，升序排序。
        n=len(grid)
        edges=[]
        for i in range(n):
            for j in range(n):
                p = i*n+j
                if i<n-1:
                    edges.append([max(grid[i][j],grid[i+1][j]),p,p+n])
                if j<n-1:
                    edges.append([max(grid[i][j],grid[i][j+1]),p,p+1])
        edges.sort()

        #并查集初始化
        father={i:i for i in range(n*n)}
        def find(x):
            if x!=father[x]:
                father[x]=find(father[x])
            return father[x]
        def union(x,y):
            a=find(x)
            b=find(y)
            father[a]=b

        #从小到大遍历加入每一条边，如果加入一条边后，首尾联通，那么返回加入的边长
        for edge in edges:
            union(edge[1],edge[2])
            if find(0)==find((n*n)-1):
                return edge[0]

        return 0

[zzzpppy]

class Solution { int[][] dirs = new int[][]{{1,0}, {-1,0}, {0,1}, {0,-1}}; public int swimInWater(int[][] grid) { int n = grid.length; int l = 0, r = n * n; while (l < r) { int mid = l + r >> 1; if (check(grid, mid)) { r = mid; } else { l = mid + 1; } } return r; } boolean check(int[][] grid, int time) { int n = grid.length; boolean[][] visited = new boolean[n][n]; Deque<int[]> queue = new ArrayDeque<>(); queue.addLast(new int[]{0, 0}); visited[0][0] = true; while (!queue.isEmpty()) { int[] pos = queue.pollFirst(); int x = pos[0], y = pos[1]; if (x == n - 1 && y == n - 1) return true;

        for (int[] dir : dirs) {
            int newX = x + dir[0], newY = y + dir[1];
            int[] to = new int[]{newX, newY};
            if (inArea(n, newX, newY) && !visited[newX][newY] && canMove(grid, pos, to, time)) {
                visited[newX][newY] = true;
                queue.addLast(to);
            }
        }
    }
    return false;
}
boolean inArea(int n, int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n;
}
boolean canMove(int[][] grid, int[] from, int[] to, int time) {
    return time >= Math.max(grid[from[0]][from[1]], grid[to[0]][to[1]]);
}

}

[tian-pengfei]

class Solution {

    vector<vector<int>> flag;
    bool isGet = false;
public:
    int swimInWater(vector<vector<int>>& grid) {
        int N = grid.size();
        int t = grid[0][0];
        queue<pair<int,int>>  q1;
        flag.resize(N,vector<int>(N));
        q1.emplace(0,0);
        flag[0][0] =1;
        while (true){

            bool pushed = false;
            int min_not_push = INT_MAX;
            int length = q1.size();
            for (int i = 0; i < length; ++i) {
                auto& a = q1.front();
                q1.pop();
                min_not_push =min(min_not_push,pushNe(t,q1,a,grid,pushed));
                if(!ifShouldDrop(a)){
                    q1.emplace(a);
                }
                if(isGet)return t;
            }
            if (!pushed){
                t= min_not_push;
            }
        }
    }
    bool ifShouldDrop(pair<int,int> & p){
        int N = flag.size();
        int x = p.first;int y = p.second;
        if(x-1>=0&& flag[x-1][y] ==0) return false;
        if(y-1>=0&& flag[x][y-1]==0)return false;
        if(x+1<N&&flag[x+1][y]==0) return false;
        if(y+1&&flag[x][y+1]==0) return false;
        return true;
    }

      int pushNe(int t,queue<pair<int,int>>& q,pair<int,int> & p,vector<vector<int>> grid,bool &pushed){
        int N = flag.size();
        int x = p.first;int y = p.second;
        int min_not_push=INT_MAX;
        if(x-1>=0&& flag[x-1][y] ==0){
            if(grid[x-1][y]>t)min_not_push = min(min_not_push,grid[x-1][y]);
            else{
                cout<<"["<<x-1<<","<<y<<"]";
                flag[x-1][y] =1;
                q.emplace(x-1,y);
                cout<<"["<<x-1<<","<<y<<"]";
                pushed= true;
            }
        }
        if(y-1>=0&& flag[x][y-1]==0){
            if(grid[x][y-1]>t)min_not_push = min(min_not_push,grid[x][y-1]);
            else{
                cout<<"["<<x<<","<<y-1<<"]";
                flag[x][y-1]=1;
                q.emplace(x,y-1);
                pushed= true;
            }
        }
        if(x+1<N&&flag[x+1][y]==0){
            if(grid[x+1][y]>t)min_not_push = min(min_not_push,grid[x+1][y]);
            else{
                cout<<"["<<x+1<<","<<y<<"]";
                flag[x+1][y]=1;
                pushed = true;
                q.emplace(x+1,y);
                if(x+1==N-1&&y==N-1) {
                    isGet = true;return 0;
                }
            }
        }
        if(y+1<N&&flag[x][y+1]==0){
            if(grid[x][y+1]>t)min_not_push = min(min_not_push,grid[x][y+1]);
            else{
                cout<<"["<<x<<","<<y+1<<"]";
                flag[x][y+1]=1;
                pushed = true;
                if(x==N-1&&y+1==N-1) {
                    isGet = true;return 0;
                }
                q.emplace(x,y+1);
           }
        }
        return min_not_push;
    }
};

[charlestang]

思路

只要 t 足够大，一定可以抵达最后一个格子。所以，这个题目的本质就是搜索一个足够小的 t，这种单调性决定了可以使用二分搜索。

查找一个仅够抵达最后一个点的最小值。我们可以使用广度优先搜索来确定能否到达最后一个点。

时间复杂度： 广度优先搜索，每个格子最多遍历一次，时间复杂度 O(N^2)，二分搜索时间复杂度 O(LogT)，T 是格子里的最大值。整体的时间复杂度是 O(N^2LogT)

空间复杂度： 主要是广度优先搜索用到队列和visited 数组，复杂度是 O(N^2)

代码

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

        # 确定上下届
        left = min(grid[0])
        right = max(grid[0])
        for i in range(1, n):
            left = min(left, min(grid[i]))
            right = max(right, max(grid[i]))
        while left <= right:
            mid = (left + right) // 2
            if self.check(grid, mid):
                right = mid - 1           
            else:
                left = mid + 1
        return left

    def check(self, grid: List[List[int]], t: int) -> bool:
        if grid[0][0] > t: return False

        row = len(grid)
        col = len(grid[0])
        if row == 1 and col == 1: return True
        v = [[False] * col for _ in range(row)]
        v[0][0] = True
        q = deque([(0, 0)])

        while q:
            pos = q.popleft()
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                x = pos[0] + dx
                y = pos[1] + dy
                if 0 <= x < row and 0 <= y < col and not v[x][y] and grid[x][y] <= t:
                    if x == row - 1 and y == col - 1: return True
                    q.append((x, y))
                    v[x][y] = True
        return False

[liuzekuan]

思路

• 正常的深度优先搜索会导致超时
• 因此引入二分查找降低时间复杂度，根据每次搜索的结果不断更新边界值即可

代码

• 语言支持：Java

Java Code:

class Solution {
    int d[][] = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    public int swimInWater(int[][] grid) {
        int col = grid.length;
        int row = grid[0].length;
        int low = grid[0][0];
        int high = 2500;
        while(low<high){
            int mid = (low+high)/2;
            //如果说按当前时间可以直接游到右下角，那么就缩小时间
            if(dfs(0,0,new boolean[col][row],mid,grid)){
                high = mid;
            //如果说按当前设定时间游不到右下角，那么就增加时间
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
    public boolean dfs(int x,int y,boolean visited[][],int target,int h[][]){
        if (x == h.length-1 && y == h[0].length-1) { return true;}
        for(int i=0;i<4;i++){
            int newx = x + d[i][0];
            int newy = y + d[i][1];
            if(newx>=0&&newx<=h.length-1&&newy>=0&&newy<=h[0].length-1&&!visited[newx][newy]&&h[newx][newy]<=target){
                visited[newx][newy] = true;
                if(dfs(newx,newy,visited,target,h)){
                    return true;
                }
            }
        }
        return false;
    }
}

复杂度分析

令 n 为数组长度。

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

[moirobinzhang]

Code:

public class Solution { public int SwimInWater(int[][] grid) {

    if (grid == null || grid.Length == 0)
        return 0;

    int left = 0;
    int right = Int32.MinValue;

    for (int i = 0; i < grid.Length; i++)
    {
        for (int j = 0; j < grid[0].Length; j++)
        {
            right = Math.Max(right, grid[i][j]);
        }
    }        

    bool[,] isVisited = new bool[grid.Length, grid[0].Length];

    while (left <= right)
    {
        int mid = (right - left) / 2 + left;

        if (IsValid(grid, isVisited, mid, 0, 0))
            right = mid - 1;
        else
            left = mid + 1 ;

        isVisited = new bool[grid.Length, grid[0].Length];            
    }

    return left; 
}

public bool IsValid(int[][] grid, bool[,] isVisited, int mid, int x, int y)
{
    if ( x < 0 || x >= grid.Length || y < 0 || y >= grid[0].Length)
        return false;

    if (grid[x][y] > mid)
        return false;

    if (x == grid.Length - 1 && y == grid[0].Length - 1)
        return true;        

    if (isVisited[x, y])
        return false;
    isVisited[x, y] = true;

    return IsValid(grid, isVisited, mid, x + 1, y) || IsValid(grid, isVisited, mid, x - 1, y) || IsValid(grid, isVisited, mid, x, y + 1 ) || IsValid(grid, isVisited, mid, x, y - 1 );

}

}

[Hacker90]

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;
}

};

[callmeerika]

思路

二分法查找限定时间内能到达右下角的最小时间

代码

var canReach = (grid, time) => {
    if (grid[0][0] > time) {
        return false;
    }
    let len = grid.length;
    let visited = new Array(len).fill(0).map(() => new Array(len).fill(false));
    visited[0][0] = true;
    let route = [[0, 0]];
    let directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    while (route.length > 0) {
        let vv = route.shift();
        let i = vv[0];
        let j = vv[1];
        for (let direction of directions) {
            let x = i + direction[0];
            let y = j + direction[1];
            if (x >= 0 && x < len && y >= 0 && y < len) {
                if (!visited[x][y] && grid[x][y] <= time) {
                    route.push([x, y]);
                    visited[x][y] = true;
                }
            }
        }
    }
    return visited[len - 1][len - 1];
}
var swimInWater = function(grid) {
    let len = grid.length;
    let left = 0;
    let right = len*len - 1;
    while (left <= right) {
        let  mid = left + Math.floor((right - left) / 2);
        if (canReach(grid, mid)) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

复杂度

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

[ozhfo]

思路

• 二分法用于寻找合适的水位
• dfs用于判断当前水位是否可以到达终点

---

代码

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;
    }
}

---

复杂度分析

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

[Moin-Jer]

思路

---

二分

代码

---

class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int left = 0, right = n * n - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (check(grid, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        } 
        return left;
    }

    public boolean check(int[][] grid, int threshold) {
        if (grid[0][0] > threshold) {
            return false;
        }
        int n = grid.length;
        boolean[][] visited = new boolean[n][n];
        visited[0][0] = true;
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{0, 0});

        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while (!queue.isEmpty()) {
            int[] square = queue.poll();
            int i = square[0], j = square[1];

            for (int[] direction : directions) {
                int ni = i + direction[0], nj = j + direction[1];
                if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
                    if (!visited[ni][nj] && grid[ni][nj] <= threshold) {
                        queue.offer(new int[]{ni, nj});
                        visited[ni][nj] = true;
                    }
                }
            }
        }
        return visited[n - 1][n - 1];
    }
}

复杂度分析

---

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

[kbfx1234]

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

// 1-22
class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        // 记录最大高度
        int maxH = 0, minH = 0;;
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                maxH = max(maxH, grid[i][j]);
            }
        }
        while (minH <= maxH) {
            int mid = (minH + maxH)/2;
            set<pair<int, int>> visited;
            if (dfs(grid, mid, 0, 0, visited)) maxH = mid - 1;
            else minH = mid + 1;

        }
        return minH;
    }
private:
    bool dfs(vector<vector<int>>& grid, int mid, int x , int y, set<pair<int, int>>& visited) {

        int m = grid.size();
        int n = grid[0].size();
        if (x < 0 || x >= m || y < 0 || y >= n) return false;
        if (grid[x][y] > mid) return false;
        if (visited.count({x,y})) return false;
        if (x == m - 1 && y == n -1) return true;

        visited.insert({x,y});

        bool ans = dfs(grid, mid, x, y - 1,visited) || dfs(grid, mid, x, y + 1,visited) 
                    || dfs(grid, mid, x - 1,y,visited) || dfs(grid, mid, x + 1, y,visited);

        return ans;
    }
};

[Arya-03]

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        def dfs(t, x, y, visited):
            if x == y == n - 1:
                return True
            visited[x][y] = True
            for dx, dy in ((-1,0),(1,0),(0,-1),(0,1)):
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and grid[nx][ny] <= t:     
                    if dfs(t, nx, ny, visited):
                        return True
            return False

        left = max(grid[0][0], grid[-1][-1])
        right = n * n - 1
        while left <= right:
            mid = (left + right) // 2
            visited = [[False] * n for _ in range(n)]
            if dfs(mid, 0, 0, visited):
                right = mid - 1
            else:
                left = mid + 1
        return left