题目描述

给你一个 m * n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。如果您最多可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1。

示例 1：
输入：
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).

示例 2：
输入：
grid =
[[0,1,1],
[1,1,1],
[1,0,0]],
k = 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

题解

  • DFS(or BFS)
  • 三维数组表示状态，(x,y,k)表示可用消除次数为k时，从(x,y)到达右下角的最短路径长度。 
class Solution {
    public static final int max=1601;
     public int shortestPath(int[][] grid, int k) {
        boolean[][] gone = new boolean[grid.length][grid[0].length];
        // 当k足够大时，最短路径是边线。公n+m-1个点，左上角和右下角为空，所以最多需要消除n+m-3次。
        k=Math.min(k,grid.length+grid[0].length-3);
        // 每个位置（x,y）在可消除障碍物次数为k的情况下，到达右下角的最短路径。
        int[][][]mins=new int[grid.length][grid[0].length][k+1];
        int res= solve(0, 0, grid, k,gone,mins);
        res=res>=max?-1:res;
        return res;
    }

    public int solve(int startX, int startY, int[][] grid, int curK, boolean[][] gone,int[][][]mins) {
        // 边界
        if (startX < 0 || startX >= grid.length || startY < 0 || startY >= grid[0].length) {
            return max;
        }

        // 到达终点
        if (startX == grid.length - 1 && startY == grid[0].length - 1) {
            return 0;
        }
        // 同一条路径中不重复
        if(gone[startX][startY]){
            return max;
        }
        // 处理过的状态直接返回
        if(mins[startX][startY][curK]!=0){
            return mins[startX][startY][curK];
        }
        gone[startX][startY] = true;//当前路径走过的点
        int min=0;
        // 障碍可消除or空
        if (grid[startX][startY] == 1&&curK>0||grid[startX][startY]==0) {
            if(grid[startX][startY]==1) {
                --curK;
            }
            int a = solve(startX - 1, startY, grid, curK, gone,mins);
            int b = solve(startX + 1, startY, grid, curK, gone,mins);
            int c = solve(startX, startY - 1, grid, curK, gone,mins);
            int d = solve(startX, startY + 1, grid, curK, gone,mins);
            min = myMin(a, b, c, d)+1;
        }else{
            min=max;//不可达
        }
        gone[startX][startY]=false;// 回溯
        return mins[startX][startY][curK]=min;
    }

    public int myMin(int a, int b, int c, int d) {
        int x = Math.min(a, b);
        int y = Math.min(c, d);
        return Math.min(x, y);
    }
}