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

[azl397985856]

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

入选理由

暂无

题目地址

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

前置知识

暂无

题目描述

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

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

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

示例 1:

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

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

输入: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]] 输出: 16 解释: 0 1 2 3 4 24 23 22 21 5 12 13 14 15 16 11 17 18 19 20 10 9 8 7 6

最终的路线用加粗进行了标记。 我们必须等到时间为 16，此时才能保证平台 (0, 0) 和 (4, 4) 是连通的

提示:

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

[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)

[DrinkMorekaik]

const swimInWater = function (grid) {
    let left = 0,right = Math.max(...grid.flat())
    const len = grid.length
    while (left <= right) {
        const mid = ((right - left) >> 1) + left
        const set = new Set()
        if (test(mid, 0, 0, set)) {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return left

    function test(mid, x, y, set) {
        if (x < 0 || x > len - 1 || y < 0 || y > len - 1) return false
        if (grid[x][y] > mid) return false
        if (x === len - 1 && y === len - 1) return true
        if (set.has(`${x}-${y}`)) return false
        set.add(`${x}-${y}`) // 记录已走过的路
        return test(mid, x - 1, y, set) || test(mid, x + 1, y, set) || test(mid, x, y - 1, set) || test(mid, x, y + 1, set)
    }

};

[zol013]

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        '''
        l, r = 0, max([max(row) for row in grid])
        seen = set()
        n = len(grid)
        def test(mid, x, y):
            if not (0 <= x < n and 0 <= y < n ):
                return False
            if grid[x][y] > mid:
                return False
            if x == y == n - 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))

[lp1506947671]

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

复杂度分析

• 时间复杂度：O(NlogM)，其中 M 为 grid 中的最大值， N 为 grid 的总大小。
• 空间复杂度：O(N)，其中 N 为 grid 的总大小。

[JiangyanLiNEU]

• DFS with memorization
• T = O(MN) M = len(grid) N = len(grid[0])

• S = O(MN)

  class Solution:
  def swimInWater(self, grid: List[List[int]]) -> int:
      self.res = float('inf')
      self.directions = [[1,0],[-1,0],[0,1],[0,-1]]
      memo = {}
  
      def inBound(row, col):
          return row >= 0 and row < len(grid) and col >= 0 and col<len(grid[0])
  
      def dfs(row, col, cur, seen):
          if (row, col) not in memo:
              memo[(row, col)] = cur
          else:
              if cur >= memo[(row, col)]:
                  return
              else:
                  memo[(row, col)] = cur
          if row == len(grid)-1 and col == len(grid[0])-1:
              self.res = min(self.res, cur)
              return
          seen.add((row, col))
          for dx, dy in self.directions:
              newX, newY = row+dx, col+dy
              if inBound(newX, newY) and (newX, newY) not in seen:
                  dfs(newX, newY, cur if grid[newX][newY] <= grid[row][col] else max(cur, grid[newX][newY]), seen)
          seen.remove((row, col))
  
      dfs(0, 0, grid[0][0], set())
      return self.res

[NorthSeacoder]

var swimInWater = function (grid) {
    //t 定义域[grid[n-1][n-1],max(grid)];
    const n = grid.length;
    const max = Math.max(...grid.map((arr) => Math.max(...arr)));
    let left = grid[n - 1][n - 1],
        right = max;
    while (left <= right) {
        const mid = left + ((right - left) >> 1);
        if (canPass(mid, grid)) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return left;
};
const canPass = (t, grid) => {
    const n = grid.length;
    const seen = new Set();
    const passPoint = (i, j) => {
        if (i < 0 || j < 0 || i > n - 1 || j > n - 1 || grid[i][j] > t) return false;
        if (i == n - 1 && j == n - 1) {
            return true;
        }
        let key = `${i}-${j}`;
        if (seen.has(key)) return false;
        seen.add(key);
        return passPoint(i + 1, j) || passPoint(i, j + 1) || passPoint(i - 1, j) || passPoint(i, j - 1);
    };
    return passPoint(0, 0);
};

• TC:O((n^2)*logmax)
• SC:O(n^2)//seen

[Lrwhc]

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

[bookyue]

TC: O(n^2lgn)
SC; O(n^2)

binary-search

    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, mid, new boolean[n][n]))
                right = mid;
            else
                left = mid + 1;
        }

        return left;
    }

    private boolean feasible(int[][] grid, int x, int y, int depth, boolean[][] visited) {
        visited[x][y] = true;

        for (int[] dir : DIRS) {
            int nx = x + dir[0];
            int ny = y + dir[1];

            if (nx < 0 || nx >= grid.length || ny < 0 || ny >= grid.length
                    || visited[nx][ny] || depth < grid[nx][ny]) continue;

            if (nx == grid.length - 1 && ny == nx) return true;
            if (feasible(grid, nx, ny, depth, visited)) return true;
        }

        return false;
    }

union-find

    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    private int n;

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

        UF uf = new UF(len);
        for (int i = 0; i < len; i++) {
            int x = index[i] / n;
            int y = index[i] % n;

            int idx = getIndex(x, y);
            for (int[] dir : DIRS) {
                int nx = x + dir[0];
                int ny = y + dir[1];

                if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] <= i)
                    uf.union(idx, getIndex(nx, ny));

                if (uf.find(0) == uf.find(len - 1))
                    return i;
            }
        }

        return -1;
    }

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

    private static class UF {
        private final int[] parent;
        private final int[] rank;

        UF(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++)
                parent[i] = i;
        }

        int find(int p) {
           while (p != parent[p]) {
               parent[p] = parent[parent[p]];
               p = parent[p];
           }

           return p;
        }

        void union(int p, int q) {
            int pRoot = find(p);
            int qRoot = find(q);

            if (pRoot == qRoot) return;

            if (rank[pRoot] >= rank[qRoot])
                parent[qRoot] = pRoot;
            else
                parent[pRoot] = qRoot;

            if (rank[pRoot] == rank[qRoot])
                rank[pRoot]++;
        }
    }

[Horace7]

const swimInWater = function (grid) {
    let left = 0,right = Math.max(...grid.flat())
    const len = grid.length
    while (left <= right) {
        const mid = ((right - left) >> 1) + left
        const set = new Set()
        if (test(mid, 0, 0, set)) {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return left

    function test(mid, x, y, set) {
        if (x < 0 || x > len - 1 || y < 0 || y > len - 1) return false
        if (grid[x][y] > mid) return false
        if (x === len - 1 && y === len - 1) return true
        if (set.has(`${x}-${y}`)) return false
        set.add(`${x}-${y}`)
        return test(mid, x - 1, y, set) || test(mid, x + 1, y, set) || test(mid, x, y - 1, set) || test(mid, x, y + 1, set)
    }

};

[FlipN9]

/**
    Approach 1: 二分查找 最短的等待时间, 看能不能找到一条路径
    TC: O(N ^ 2 logN)   SC: O(N^2)
            4ms
*/
class Solution {
    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;
    }
}

[GuitarYs]

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

[Abby-xu]

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 

[aswrise]

def nbs(ab, N):
    [a,b]=ab
    res=[]
    if a>0:
        res=res+[[a-1,b]]
    if a<=N-2:
        res=res+[[a+1,b]]
    if b>0:
        res=res+[[a,b-1]]
    if b<=N-2:
        res=res+[[a,b+1]]
    return res

def search(grid, waterlevel):
    N=len(grid)

    #start at:

    if grid[0][0]<=waterlevel and grid[N-1][N-1]<=waterlevel:
        base=[[0,0]]  #the list of reachable places.
    else:
        return False 

    for elem in base:
        for [a,b] in nbs(elem, N):
            if grid[a][b]<=waterlevel:
                if  not [a,b] in base:
                    if a==N-1 and b==N-1:
                        return True
                    else:
                        base.append([a,b])
    #print('false: lev=',waterlevel, base)
    return False    

def swim(grid):
#def swimInWater(self, grid: List[List[int]]) -> int:
    N=len(grid)
    if N==1:
        return grid[0][0]

    if grid[0][0]<= grid[N-1][N-1]:
        s= grid[0][0]-1
    else:
        s=grid[N-1][N-1] -1
    t=max([max(l) for l in grid])

    #bin search??
    while t-s>=2:
        mid = int((s+t)/2)
        res = search(grid, mid)
        print(mid,res)
        if res==True:
            t=mid
        else:
            s=mid
    return t

class Solution:

    def swimInWater(self, grid):
        return swim(grid)

[tzuikuo]

思路

优先级队列

代码

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int m=grid.size(),n=grid[0].size();
        int re=0;
        vector<vector<int>> direc={{1,0},{-1,0},{0,-1},{0,1}};
        priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> pq;

        pq.push({grid[0][0],{0,0}});
        grid[0][0]=-1;
        while(!pq.empty()){
            int sz=pq.size();
            while(sz--){
                pair<int,pair<int,int>> cur;
                cur=pq.top();
                pq.pop();
                re=max(re,cur.first);
                if(cur.second.first==m-1&&cur.second.second==n-1) return re;
                for(int i=0;i<=3;i++){
                    int x=direc[i][0]+cur.second.first;
                    int y=direc[i][1]+cur.second.second;
                    if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]!=-1){
                        pq.push({grid[x][y],{x,y}});
                        grid[x][y]=-1;
                    }
                }
            }
        }

        return re;
    }

};

复杂度分析

• 时间待定
• 空间O(n)

[linlizzz]

思路

1. 总的对[0, max_depth]进行最左边界的二分，求能到达右下角的最小深度

2. 二分时判断函数是对二维平面进行DFS

** 注意记录搜索时已访问过的点集合visited

** 注意每次清空集合visited

(看了官方题解再做的)

代码

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

        def reached(depth, x, y):
            if x > N-1 or x < 0 or y > N-1 or y < 0:
                return False
            elif grid[x][y] > depth:
                return False
            elif (x, y) in visited:
                return False
            elif x == N-1 and y == N-1:
                return True
            else:
                visited.add((x, y))
                res = reached(depth, x+1, y) or reached(depth, x-1, y) or reached(depth, x, y+1) or reached(depth, x, y-1)
            return res

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

        while l <= r:
            visited = set()
            mid = (l+r)//2
            if reached(mid, 0, 0):
                r = mid - 1
            else:
                l = mid + 1

        return l

复杂度分析

T(n) = O(n^2logm), n=len(grid), m = max([max(i) for i in grid])

S(n) = O(n^2)

[FireHaoSky]

思路：二分法

代码：python

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

        while l < r:
            mid = l + (r-l)//2
            if grid[0][0] <= mid and self.check(grid,mid,n):
                r = mid
            else:
                l = mid + 1
        return l

    def check(self,grid, mid,n):
        queue = collections.deque()
        queue.append((0,0))

        visited = [[False] * n for i in range(n)]
        visited[0][0] = True

        while queue:
            x,y = queue.popleft()

            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] <= mid:
                    queue.append((nx,ny))
                    visited[nx][ny] = True
                    if (nx,ny) == (n-1,n-1):
                        return True

        return False

复杂度分析：

"""
时间复杂度：O(n^2logn)
空间复杂度:O（n^2）
"""

[Meisgithub]

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        int left = 0;
        int right = n * n - 1;
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            vector<vector<bool>> visited(n, vector<bool>(n, false));
            visited[0][0] = true;
            vector<vector<int>> uMap(n, vector<int>(n, -1));
            if (isArrive(grid, 0, 0, visited, mid, uMap))
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }
        return left;
    }

    bool isArrive(vector<vector<int>>& grid, int i, int j, vector<vector<bool>>& visited, int t, vector<vector<int>>& uMap)
    {
        if (uMap[i][j] != -1)
        {
            return uMap[i][j];
        }
        if (i == grid.size() - 1 && j == grid.size() - 1)
        {
            if (grid[i][j] > t)
            {
                uMap[i][j] = 0;
                return false;
            }
            uMap[i][j] = true;
            return true;
        }
        if (i - 1 >= 0 && t >= grid[i - 1][j] && t >= grid[i][j] && !visited[i - 1][j])
        {
            visited[i - 1][j] = true;
            if (isArrive(grid, i - 1, j, visited, t, uMap))
            {
                uMap[i][j] = true;
                return true;
            }
            visited[i - 1][j] = false;
        }
        if (i + 1 < grid.size() && t >= grid[i + 1][j] && t >= grid[i][j] && !visited[i + 1][j])
        {
            visited[i + 1][j] = true;
            if (isArrive(grid, i + 1, j, visited, t, uMap))
            {
                uMap[i][j] = true;
                return true;
            }
            visited[i + 1][j] = false;
        }
        if (j - 1 >= 0 && t >= grid[i][j - 1] && t >= grid[i][j] && !visited[i][j - 1])
        {
            visited[i][j - 1] = true;
            if (isArrive(grid, i, j - 1, visited, t, uMap))
            {
                uMap[i][j] = true;
                return true;
            }
            visited[i][j - 1] = false;
        }
        if (j + 1 < grid.size() && t >= grid[i][j + 1] && t >= grid[i][j] && !visited[i][j + 1])
        {
            visited[i][j + 1] = true;
            if (isArrive(grid, i, j + 1, visited, t, uMap))
            {
                uMap[i][j] = true;
                return true;
            }
            visited[i][j + 1] = false;
        }
        uMap[i][j] = false;
        return false;
    }
};

[kofzhang]

思路

二分，深度优先搜索

复杂度

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

代码

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

        def possible(t):
            temp_grid = [[False]*n for _ in range(n)]

            def dfs(x,y,t):
                if y<0 or x<0 or y==n or x==n:
                    return     
                if temp_grid[x][y]==True:
                    return 
                if grid[x][y]<=t:                    
                    temp_grid[x][y] = True 
                    if x == n - 1 and y == n - 1:
                        return                   
                    dfs(x+1,y,t)
                    dfs(x-1,y,t)
                    dfs(x,y+1,t)
                    dfs(x,y-1,t)
            dfs(0,0,t)
            if temp_grid[n-1][n-1]==True:
                return True
            return False
        while l<r:
            mid = l+r>>1
            if possible(mid):
                r = mid
            else:
                l = mid + 1
        return l

[duke-github]

思路

二分查找高度的数量 并且深度遍历直到尾点

复杂度

时间复杂度O(n*n*logn) 空间复杂度O(n*n)

代码

class Solution {
    private static int N;

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

    public static int swimInWater(int[][] grid) {
        int len = grid.length;
        N = len;
        int start = 0, end = len * len -1 , temp;
        //二分查找
        while (start < end) {
            temp = (start + end) / 2;
            //记录已经深度遍历过的点
            boolean[][] visited = new boolean[len][len];
            //第一个点小于当前判断的值 并且深度遍历其他的点
            if (grid[0][0] <= temp && dfs(grid, visited, 0, 0, temp)) {
                end = temp;
            } else {
                start = temp + 1;
            }
        }
        return start;
    }

    //深度遍历所有的点
    private static boolean dfs(int[][] grid, boolean[][] visited, int x, int y, int temp) {
        visited[x][y] = true;
        //四个方向
        for (int[] direction : DIRECTIONS) {
            int newX = x + direction[0];
            int newY = y + direction[1];
            //遍历到最后一个点的时候 并且最后一个点小于当前的高度  证明存在这个路径了
            if (newX == N - 1 && newY == N - 1 && grid[newX][newY] <= temp) {
                return true;
            }
            //点存在 未遍历 不高于当前高度 就继续深度遍历
            if (isArea(newX, newY) && !visited[newX][newY] && grid[newX][newY] <= temp && dfs(grid, visited, newX, newY, temp)) {
                return true;
            }
        }
        return false;
    }

    public static boolean isArea(int x, int y) {
        return x >= 0 && y >= 0 && x < N && y < N;
    }
}

[KrabbeJing]

思路

二分查找

代码

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        l, r = 0, max([max(row) for row in grid])
        M, N = len(grid), len(grid[0])
        seen = set()
        def is_pass(value, x, y):
            if x >= M or y >= N or x < 0 or y < 0:
                return False
            if value < grid[x][y]:
                return False
            if (x, y) == (M-1, N-1):
                return True
            if (x, y) in seen:
                return False
            seen.add((x, y))
            ans = (is_pass(value, x + 1, y) 
                    or is_pass(value, x - 1, y)
                    or is_pass(value, x, y - 1)
                    or is_pass(value, x, y + 1))
            return ans

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

[wangzh0114]

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

• TC:O(n^2logn)
• SC:O(n^2)

[chanceyliu]

代码

const check = (grid, threshold) => {
  if (grid[0][0] > threshold) {
    return false;
  }
  const n = grid.length;
  const visited = new Array(n).fill(0).map(() => new Array(n).fill(false));
  visited[0][0] = true;
  const queue = [[0, 0]];

  const directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];
  while (queue.length) {
    const square = queue.shift() || [];
    const i = square[0];
    const j = square[1];

    for (const direction of directions) {
      const 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.push([ni, nj]);
          visited[ni][nj] = true;
        }
      }
    }
  }
  return visited[n - 1][n - 1];
};

function swimInWater(grid: number[][]): number {
  const n = grid.length;
  let left = 0,
    right = n * n - 1;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (check(grid, mid)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
}

复杂度分析

• 时间复杂度：O(n2 logn)
• 空间复杂度：O(n2)

[snmyj]

public static int swimInWater(int[][] grid) {
        int n = grid.length;
        int lo = Math.max(grid[0][0], grid[n - 1][n - 1]);

        int hi = findMax(grid);

        if(grid[n - 1][n - 1] == hi){
            return hi;
        }

        BitSet bs = new BitSet(hi);

        while (lo < hi) {
            int mi = (lo + hi) >> 1;
            if (dfs(grid, 0, 0, mi, bs)) {
                hi = mi;
            } else {
                lo = mi + 1;
            }
            bs.clear();
        }

        return lo;
    }

    public static int findMax(int[][] grid){
        int max = -1;
        for (int[] ints : grid) {
            for (int anInt : ints) {
                max = Math.max(max, anInt);
            }
        }
        return max;
    }

    public static boolean dfs(int[][] grid, int i, int j, int limit, BitSet bs) {
        if (bs.get(i * grid.length + j) || grid[i][j] > limit) {
            return false;
        }
        if (i == grid.length - 1 && j == grid.length - 1) {
            return true;
        }
        bs.set(i * grid.length + j);
        if (i < grid.length - 1 && dfs(grid, i + 1, j, limit, bs)) {
            return true;
        }
        if (j < grid.length - 1 && dfs(grid, i, j + 1, limit, bs)) {
            return true;
        }
        if (i > 0 && dfs(grid, i - 1, j, limit, bs)) {
            return true;
        }
        if (j > 0 && dfs(grid, i, j - 1, limit, bs)) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {

        int[][] grid = {{0, 1, 2, 3, 4}, {24, 23, 22, 21, 5}, {12, 13, 14, 15, 16}, {11, 17, 18, 19, 49}, {10, 9, 8, 47, 50}};
        int res = swimInWater(grid);
        System.out.println(res);
    }

[harperz24]

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        def bfs(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 bfs(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 bfs(mid, 0, 0, visited):
                right = mid - 1
            else:
                left = mid + 1
        return left

[Hughlin07]

class Solution {

public int swimInWater(int[][] grid) {
    int N = grid.length;
    int lo = grid[0][0], hi = N * N;
    while (lo < hi) {
        int mi = lo + (hi - lo) / 2;
        if (!possible(mi, grid)) {
            lo = mi + 1;
        } else {
            hi = mi;
        }
    }
    return lo;
}

public boolean possible(int T, int[][] grid) {
    int N = grid.length;
    Set<Integer> seen = new HashSet();
    seen.add(0);
    int[] dr = new int[]{1, -1, 0, 0};
    int[] dc = new int[]{0, 0, 1, -1};

    Stack<Integer> stack = new Stack();
    stack.add(0);

    while (!stack.empty()) {
        int k = stack.pop();
        int r = k / N, c = k % N;
        if (r == N-1 && c == N-1) return true;

        for (int i = 0; i < 4; ++i) {
            int cr = r + dr[i], cc = c + dc[i];
            int ck = cr * N + cc;
            if (0 <= cr && cr < N && 0 <= cc && cc < N
                    && !seen.contains(ck) && grid[cr][cc] <= T) {
                stack.add(ck);
                seen.add(ck);
            }
        }
    }

    return false;
}

}

Time:O((N^2)logN). Space: O(N^2)

[wwewwt]

思路

模拟水位上升的过程，不断更新所能游到的新位置，直到最后出现了[N-1,N-1]

代码

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        N = len(grid)
        max = 0
        water_level = grid[0][0]
        #起始位
        lake = []
        lake.append([0,0])

        while True:
            i=0
            while i < len(lake):
                #左移动一格
                if lake[i][0] - 1 >= 0:
                    #如果水位小于等于当前点，则可以游过去
                    if grid[lake[i][0] - 1][lake[i][1]] <= water_level and [lake[i][0] - 1, lake[i][1]] not in lake:
                        lake.append([lake[i][0] - 1, lake[i][1]])

                if lake[i][0] + 1 <= N-1:
                    if grid[lake[i][0] + 1][lake[i][1]] <= water_level and [lake[i][0] + 1, lake[i][1]] not in lake:
                        lake.append([lake[i][0] + 1, lake[i][1]])

                if lake[i][1] - 1 >= 0:
                    if grid[lake[i][0]][lake[i][1] - 1] <= water_level and [lake[i][0], lake[i][1] - 1] not in lake:
                        lake.append([lake[i][0], lake[i][1] - 1])

                if lake[i][1] + 1 <= N-1:
                    if grid[lake[i][0]][lake[i][1] + 1] <= water_level and [lake[i][0], lake[i][1] + 1] not in lake:
                        lake.append([lake[i][0], lake[i][1] + 1])
                i+=1

            if [N-1,N-1] in lake:
                return water_level

            water_level += 1

复杂度

时间复杂度：O(n2) 空间复杂度：O(n)

[kyo-tom]

思路

并查集

代码

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

复杂度分析 时间复杂度：n^2*O(logn) 空间复杂度：O(N^2)

[AstrKing]

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

}

[kangliqi1]

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

}

[JingYuZhou123]

/**
 * @param {number[][]} grid
 * @return {number}
 */
var swimInWater = function (grid) {
    const n = grid.length;
    let start = 0;
    let end = n * n - 1;

    let min = 0;
    while (start <= end) {
        const mid = Math.floor((start + end) / 2);
        const res = checkAvalibalePath(grid, mid);
        if (res) {
            end = mid - 1;
            min = mid;
        } else {
            start = mid + 1;
        }
    }
    return min;
};

const checkAvalibalePath = (grid, t) => {
    const n = grid.length;
    const directions = [
        [0, 1],
        [0, -1],
        [1, 0],
        [-1, 0],
    ];
    const visited = new Array(n).fill(false).map(() => new Array(n).fill(false));

    const dfs = (i, j) => {
        if (visited[i][j] || grid[i][j] > t) {
            return;
        }

        visited[i][j] = true;
        for (const dir of directions) {
            const dx = i + dir[0];
            const dy = j + dir[1];
            if (dx < 0 || dx >= n || dy < 0 || dy >= n) {
                continue;
            }

            dfs(dx, dy);
        }
    };
    dfs(0, 0);
    return visited[n - 1][n - 1];
};

[JasonQiu]

• Dijkstra

  class Solution(object):
  def swimInWater(self, grid):
      n = len(grid)
      heap = []
      heapq.heappush(heap, (grid[0][0], 0, 0))
      visited = {0 * n + 0: 1}
      directions = [-1, 0, 1, 0, -1]
  
      while heap:
          cell = heapq.heappop(heap)
          if cell[1] == n - 1 and cell[2] == n - 1:
              return cell[0]
          for i in range(4):
              next_x = cell[1] + directions[i]
              next_y = cell[2] + directions[i + 1]
              if next_x < 0 or next_y < 0 or next_x >= n or next_y >= n or visited.get(next_x * n + next_y):
                  continue
              visited[next_x * n + next_y] = 1
              heapq.heappush(heap, (max(cell[0], grid[next_y][next_x]), next_x, next_y))

  Time: O((n^2)logn) Space: O(n^2)

[RestlessBreeze]

code

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

[yingchehu]

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

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

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

[joemonkeylee]

思路

这个题超出能力范围了。mark

代码

    private int N;

        private int[][] DIR = { new[] { 0, 1 }, new[] { 0, -1 }, new[] { 1, 0 }, new[] { -1, 0 } };

        public int SwimInWater(int[][] grid)
        {
            N = grid.Length;

            var left = 0;
            var right = N * N - 1;
            while (left < right)
            {
                var mid = (left + right) / 2;

                if (grid[0][0] <= mid && bfs(grid, mid))
                {
                    right = mid;
                }
                else
                {
                    left = mid + 1;
                }
            }

            return left;
        }

        private bool bfs(int[][] grid, int threshold)
        {
            var queue = new Queue<(int x, int y)>();
            queue.Enqueue((0, 0));
            var visited = new bool[N, N];
            visited[0, 0] = true;

            while (queue.Count != 0)
            {
                var (x, y) = queue.Dequeue();
                foreach (var direction in DIR)
                {
                    var newX = x + direction[0];
                    var newY = y + direction[1];
                    if (!inArea(newX, newY) || visited[newX, newY] || grid[newX][newY] > threshold) continue;
                    if (newX == N - 1 && newY == N - 1) return true;
                    queue.Enqueue((newX, newY));
                    visited[newX, newY] = true;
                }
            }

            return false;
        }

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

复杂度分析

• 时间复杂度：O(n2logn)
• 空间复杂度：O(n2)

[X1AOX1A]

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:        
        seen = set()
        def dfs(mid, x, y):
            # (x, y) 超过边界
            if x > len(grid) - 1 or x < 0 or y > len(grid[0]) - 1 or y < 0:
                return False
            # grid>mid, 返回 false，向右查找
            if grid[x][y] > mid:
                return False
            # 已走过，返回 false，避免重复
            if (x, y) in seen:
                return False
            # 到达右下角，返回 true
            if (x, y) == (len(grid) - 1, len(grid[0]) - 1):
                return True                
            seen.add((x, y))
            # 遍历四个方向
            ans = dfs(mid, x + 1, y) or \
                  dfs(mid, x - 1, y) or \
                  dfs(mid, x, y + 1) or \
                  dfs(mid, x, y - 1)
            return ans

        # 计数二分
        l, r = 0, max([max(vec) for vec in grid])
        while l <= r:
            mid = (l + r) // 2
            if dfs(mid, 0, 0):
                r = mid - 1
            else:
                l = mid + 1
            seen = set()
        return l

[aoxiangw]

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        N = len(grid)
        visit = set()
        minH = [[grid[0][0], 0, 0]]
        directions = [[0,1], [0,-1], [1,0], [-1,0]]
        visit.add((0,0))
        while minH:
            t, r, c = heapq.heappop(minH)
            visit.add((r,c))
            if r == N - 1 and c == N - 1:
                return t
            for dr, dc in directions:
                neiR, neiC = r + dr, c + dc
                if (neiR < 0 or neiC < 0 or
                    neiR == N or neiC == N or
                    (neiR, neiC) in visit):
                    continue
                visit.add((neiR, neiC))
                heapq.heappush(minH, [max(t, grid[neiR][neiC]), neiR, neiC])

time, space: O(n^2logn), O(n^2)

[SoSo1105]

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

[Lydia61]

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

思路

官方二分法

代码

class Solution {
public:
    bool check(vector<vector<int>>& grid, int threshold) {
        if (grid[0][0] > threshold) {
            return false;
        }
        int n = grid.size();
        vector<vector<int>> visited(n, vector<int>(n, 0));
        visited[0][0] = 1;
        queue<pair<int, int>> q;
        q.push(make_pair(0, 0));

        vector<pair<int, int>> directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while (!q.empty()) {
            auto [i, j] = q.front();
            q.pop();

            for (const auto [di, dj]: directions) {
                int ni = i + di, nj = j + dj;
                if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
                    if (visited[ni][nj] == 0 && grid[ni][nj] <= threshold) {
                        q.push(make_pair(ni, nj));
                        visited[ni][nj] = 1;
                    }
                }
            }
        }
        return visited[n - 1][n - 1] == 1;
    }

    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        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;
    }
};

复杂度分析：

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

[jmaStella]

思路

dijkstra

代码

public int swimInWater(int[][] grid) {
        //Dijkstra
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> grid[a[0]][a[1]] - grid[b[0]][b[1]]);
        int[][] visited = new int[grid.length][grid.length];
        int[][] dir = new int[][]{{0,1}, {1,0},{-1,0},{0,-1}};
        int time = 0;
        pq.add(new int[]{0,0});

        while(!pq.isEmpty()){
            int[] curr = pq.poll();

            time = Math.max(time, grid[curr[0]][curr[1]]);

            if(curr[0] == grid.length-1 && curr[1] == grid.length-1){
                return time;
            }
            visited[curr[0]][curr[1]] = 1;
            for(int[] d: dir){

                if(curr[0]+d[0]<0 || curr[0]+d[0]>=grid.length ||curr[1]+d[1]<0 || curr[1]+d[1]>=grid.length || visited[curr[0]+d[0]][curr[1]+d[1]] == 1){
                continue;
            }
                pq.add(new int[]{curr[0]+d[0], curr[1]+d[1]});
            }
        }
        return time;
    }

复杂度

时间 O(N^2) 空间 O(N^2)

[chocolate-emperor]

class Solution {
public:

// 
// 枚举t，判断f(t)是否满足条件。 t [0,max_val]
// 对t二分搜索，找到满足 f(t) 到达 (n-1,n-1)条件的t最小值,t越大，越能满足

    bool judge(int t,vector<vector<int>>& maps,vector<vector<bool>>&vis,int x,int y){
        if(t<maps[x][y])    return false;

        int l = maps.size();
        if(x == l-1 && y == l-1)    return true;

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

        bool flag = false;
        for(int i =0; i<4; i++){
            int ne_x = x +dx[i], ne_y = y + dy[i];
            if(ne_x >= 0 && ne_x <l && ne_y >= 0 && ne_y<l){
                if(vis[ne_x][ne_y]==false && t >=maps[ne_x][ne_y]){
                    vis[ne_x][ne_y] = true;
                    flag = flag || judge(t,maps,vis,ne_x,ne_y);
                }
            }
        }
        return flag;
    }
    int swimInWater(vector<vector<int>>& grid) {
        vector<vector<bool>>vis(grid.size());
        int r = -1;
        for(int i = 0; i<grid.size();i++){
            vector<bool>tmp;
            for(int j= 0; j<grid.size();j++){
                r = max(grid[i][j],r);
                tmp.push_back(false);
            }
            vis[i] = tmp;
        }

        int l = 0;
        while(l<r){
            int mid  = (l+r)/2;
            for(int i = 0;i<grid.size();i++){
                vector<bool>tmp(grid.size(),false);
                vis[i] = tmp;
            }
            if(judge(mid,grid,vis,0,0)==false){
                l = mid+1;
            }else{
                r = mid;
            }
        }
        return l;
    }
};