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

[larscheng]

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

[larscheng]

思路

二分查找+深度优先遍历

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

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

代码

public class Solution {

    private int N;

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

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

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

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

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

复杂度

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