Leetcode 2290. Minimum Obstacle Removal to Reach Corner

[Woodyiiiiiii]

这种二维数组迷宫题，一般都用DFS/BFS，但由于时间复杂度，BFS使用多些。

我之前很少做过这种题目，不知道这种有障碍的二维数组怎么做。实际上，做法是，使用BFS，并且记录经过的障碍的数量。

那么接下来要解决两种问题：

1. 如何避免BFS出现环，也就是说避免回溯到过去路径
2. 如何规划路径，即使用队列还是优先队列

解决方法：

1. 设置多的空间，比如记录障碍数量；改变原本数组
2. 用优先路径可以提前规划好路径；或者绕过某点

这道题解决方法中，首先设置DP数组，存储[i,j]的最小障碍数量，一开始设置为整型最大值，循环中判断到下个点的障碍数量所能否小于dp[i][j]才继续BFS，所以就可以避免环的出现；然后用优先路径以最小障碍数量路径为先。

class Solution {
    public int minimumObstacles(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[2]));
        pq.offer(new int[]{0, 0, 0});
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dp[i], m * n);
        }
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            if (cur[0] == m - 1 && cur[1] == n -  1) {
                return cur[2];
            }
            for (int[] dir : dirs) {
                int x = cur[0] + dir[0], y = cur[1] + dir[1];
                if (x < 0 || x >= m || y < 0 || y >= n || cur[2] + grid[x][y] >= dp[x][y]) continue;
                dp[x][y] = cur[2] + grid[x][y];
                pq.offer(new int[]{x, y, dp[x][y]});
            }
        }
        return dp[m - 1][n - 1];
    }
}

类似题目：

• 1293. Shortest Path in a Grid with Obstacles Elimination (这道题很有意思，先以最大值为准，然后不停优化路径知道最优值；思考为什么不用Queue而用PQ——因为路径会错乱，会以步骤较少的路径为优先，而让少用obstacles的路径断绝)
• 909. Snakes and Ladders (思考为什么不用PQ)

---

• 2290. Minimum Obstacle Removal to Reach Corner