Leetcode 1631. Path With Minimum Effort

[Woodyiiiiiii]

1631. Path With Minimum Effort

1631. Path With Minimum Effort

类似题目：
1631. Path With Minimum Effort

讲解：
接近 O(n^2) 的做法：多源BFS+倒序枚举答案+并查集（Python/Java/C++/Go） (并查集)

这道题一看最小化最大值/最大化最小值，就感觉要用二分。关键是，一开始要预处理算出每个点距离所有theif节点的最近距离，然后二分答案进行BFS遍历。问题是如何在规定时间复杂度下算出距离，考虑到二分数组长度和高度最多是100，最多进行三层遍历，那该怎么办呢？考虑下只能用两层遍历了，也就是说每个点访问一遍即可，也就是多源BFS，按照队列先进先出的特性，按照顺序访问每个点，每个点访问一次就行了，每次就已经得出最小距离。

WA了三次，其中第一次我竟然用DP来遍历路径，很显然不对，DP只能右移和下移；第二次没考虑到边界情况；第三次则是TLE了。最后才是想到用PQ来做，但更好的方法是用Q就够了。

吸取教训，多源BFS。

其他方法有用并查集，或者Dijkstra。

class Solution {
    List<List<Integer>> grid;
    int[][] dp;
    int n;
    final int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int maximumSafenessFactor(List<List<Integer>> grid) {
        this.n = grid.size();
        this.dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], n + n);
        }
        this.grid = grid;
        if (grid.get(0).get(0) == 1 || grid.get(n - 1).get(n - 1) == 1) {
            return 0;
        }

        // TLE
        LinkedList<int[]> q = new LinkedList<>();
        boolean[][] v = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid.get(i).get(j) == 1) {
                    dp[i][j] = 0;
                    v[i][j] = true;
                    q.add(new int[]{i, j});
                }
            }
        }
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int[] dir : dirs) {
                int x = cur[0] + dir[0], y = cur[1] + dir[1];
                if (x < 0 || x >= n || y < 0 || y >= n || v[x][y]) {
                    continue;
                }
                dp[x][y] = Math.min(dp[x][y], dp[cur[0]][cur[1]] + 1);
                v[x][y] = true;
                q.add(new int[]{x, y});
            }
        }

        int l = 0, r = Math.min(dp[0][0], dp[n - 1][n - 1]) + 1;
        while (l < r) {
            int m = (l + r) >> 1;
            if (ok(m)) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l - 1;
    }

    private boolean ok(int m) {
        LinkedList<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0});
        boolean[][] visited = new boolean[n][n];
        visited[0][0] = true;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int[] dir : dirs) {
                int x = cur[0] + dir[0], y = cur[1] + dir[1];
                if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y] || dp[x][y] < m) {
                    continue;
                }
                if (x == n - 1 && y == n - 1) {
                    return true;
                }
                visited[x][y] = true;
                q.add(new int[]{x, y});
            }
        }
        return false;
    }
}