leetcode 1293. Shortest Path in a Grid with Obstacles Elimination | 1293. 网格中的最短路径（BFS）

https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/

DFS 递归超时，看了评论区 & 答案区，没有可运行的 DFS 解法，这题只能 BFS。疑问：DFS 的复杂度是多少？

尝试改成带缓存的递归，但是由于 visited 数组的存在，当前状态还与整个 visited 表有关，dfs(x, y, k) 三个参数不足以表示当前状态，无法加缓存，除非将 visited 数组也当做缓存的一个维度。

尝试用 dp[x][y][k] 剪枝优化，如果已经遇到过 dp[x][y][k]，且之前的 k 大于当前的 k，则剪枝，此优化几乎无效果。

总结：带有visited数组的回溯是一种有后效性的递归，无法转换成dp.

BFS 参考：Java-Straightforward-BFS-O(MNK)-time-or-O(MNK)-space

本地测过几个例子，代码应该没问题。

class Solution {
    int M;
    int N;

    public int shortestPath(int[][] grid, int k) {
        M = grid.length;
        N = grid[0].length;

        boolean[][] visited = new boolean[M][N];
        k = grid[0][0] == 1 ? k - 1 : k;
        int res = bfs(0, 0, 0, k, grid, visited);
        System.out.println(res);
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    // at position (x,y), remain k obstacles to remove
    // if valid, return min steps
    public int bfs(int steps, int x, int y, int k, int[][] grid, boolean[][] visited) {
        if (x < 0 || x >= M || y < 0 || y >= N || visited[x][y] || k < 0) return Integer.MAX_VALUE;
        if (x == M - 1 && y == N - 1) return steps;

        int t = grid[x][y] == 0 ? k : k - 1;
        visited[x][y] = true;
        int p1 = bfs(steps + 1, x, y - 1, t, grid, visited);
        int p2 = bfs(steps + 1, x, y + 1, t, grid, visited);
        int p3 = bfs(steps + 1, x - 1, y, t, grid, visited);
        int p4 = bfs(steps + 1, x + 1, y, t, grid, visited);
        visited[x][y] = false;
        return Math.min(Math.min(p1, p2), Math.min(p3, p4));
    }
}

class Solution {
    int M;
    int N;
    int[][] ways = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int shortestPath(int[][] grid, int k) {
        M = grid.length;
        N = grid[0].length;
        Queue queue = new linkedList<>();
        boolean[][][] visited = new boolean[M][N][k + 1];
        visited[0][0][0] = true;
        queue.offer(new int[]{0, 0, 0});
        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] record = queue.poll();
                int x = record[0];
                int y = record[1];
                int curK = record[2];
                if (x == M - 1 && y == N - 1) return step;
                for (int[] way : ways) { // 4个方向
                    int nextX = x + way[0];
                    int nextY = y + way[1];
                    int nextK = curK;
                    if (nextX >= 0 && nextX < M && nextY >= 0 && nextY < N) {
                        if (grid[nextX][nextY] == 1) nextK++;
                        if (nextK <= k && !visited[nextX][nextY][nextK]) {
                            visited[nextX][nextY][nextK] = true;
                            queue.offer(new int[]{nextX, nextY, nextK});
                        }
                    }
                }
            }
            step++;
        }
        return -1;
    }
}