三维BFS跨障碍找最短路径

LeetCode 1293. 网格中的最短路径 (opens new window)

题目描述

给你一个 m * n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。

如果您 最多 可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1。输入满足：

grid.length == m
grid[0].length == n
1 <= m, n <= 40
1 <= k <= m*n
grid[i][j] == 0 or 1
grid[0][0] == grid[m-1][n-1] == 0

示例

输入： 
grid = 
[[0,0,0],
 [1,1,0],
 [0,0,0],
 [0,1,1],
 [0,0,0]], 
k = 1
输出：6
解释：
不消除任何障碍的最短路径是 10。
消除位置 (3,2) 处的障碍后，最短路径是 6 。该路径是 (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).

输入：
grid = 
[[0,1,1],
 [1,1,1],
 [1,0,0]], 
k = 1
输出：-1
解释：
我们至少需要消除两个障碍才能找到这样的路径。

解题思路

使用BFS来搜索最短路径，由于是在矩阵中进行搜索，每次移动时有上下左右4种选择，那么需要进行剪枝以免重复进入到相同的点。但同时进入一个点可能有多种方向，那么不能简单地用visited[i][j]来标记（因为可能先进入到该点的路径消耗了更多的清除障碍次数，导致可能消耗更少清除障碍次数到达该点的路径被忽略），所以还需要增加一维表示还剩k次清除机会时是否进入过该点，这样当首次达到终点时计数的层数就是结果。

public class No1293_ShortestPathWithObstacles {

    public int shortestPath(int[][] grid, int k) {
        final int[][] direction = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int m = grid.length, n = grid[0].length, step = 0;
        k = Math.min(k, m + n - 3);
        boolean[][][] visited = new boolean[m][n][k + 1];
        Queue<Point> queue = new LinkedList<>();

        queue.offer(new Point(0, 0, k));
        visited[0][0][k] = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                Point cur = queue.poll();
                if (cur.x == m - 1 && cur.y == n - 1) return step;
                for (int[] dir : direction) {
                    int i = cur.x + dir[0], j = cur.y + dir[1];
                    if (0 > i || i >= m || 0 > j || j >= n) continue;
                    int rest = cur.remain - grid[i][j];
                    if (rest >= 0 && !visited[i][j][rest]) {
                        visited[i][j][rest] = true;
                        queue.offer(new Point(i, j, cur.remain - grid[i][j]));
                    }
                }
            }
            step++;
        }
        return -1;
    }

    class Point{
        int x;
        int y;
        int remain;

        public Point(int x, int y, int remain) {
            this.x = x;
            this.y = y;
            this.remain = remain;
        }
    }
}