【Day 42 】2024-05-19 - 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] 内。

[xil324]

import heapq
class Solution(object):
    def swimInWater(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        n = len(grid); 
        heap = [(grid[0][0], 0,0)]; 
        count = 0
        visited = set(); 
        while heap:
            time, row, col = heapq.heappop(heap); 
            count = max(time, count); 
            if row == n-1 and col == n-1:
                return count; 
            for direction in [(0,-1), (0,1), (1,0), (-1,0)]:
                x = direction[0] + row
                y = direction[1] + col
                if 0 <=x < len(grid) and 0<=y< len(grid[0]) and (x,y) not in visited: 
                    heapq.heappush(heap, (grid[x][y], x,y)); 
                    visited.add((x,y))
        return count; 

[franklinsworld666]

from typing import List, Tuple
from collections import deque

class Solution:
    def canReach(self, time: int, matrix: List[List[int]]) -> bool:
        rows, cols = len(matrix), len(matrix[0])
        queue: deque[Tuple[int, int]] = deque([(0, 0)])
        visit = [[0] * cols for _ in range(rows)]
        visit[0][0] = 1

        while queue:
            x, y = queue.popleft()
            if x == rows - 1 and y == cols - 1:
                return True

            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < rows and 0 <= ny < cols and matrix[nx][ny] <= time and not visit[nx][ny]:
                    visit[nx][ny] = 1
                    queue.append((nx, ny))

        return False

    def swimInWater(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        low, high = max(grid[0][0], grid[-1][-1]), max([max(row) for row in grid])
        res = rows * cols

        while low <= high:
            mid = (low + high) // 2
            if self.canReach(mid, grid):
                res = min(res, mid)
                high = mid - 1
            else:
                low = mid + 1

        return res

复杂度

时间复杂度：O(N^2logN) 空间复杂度：O(N^2)

[Dtjk]

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

    }
};