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

迈不过友情╰ 2022-09-12 14:46 42阅读 0赞

## 题目 ##

[https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/][https_leetcode.com_problems_shortest-path-in-a-grid-with-obstacles-elimination]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

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][Java-Straightforward-BFS-O_MNK_-time-or-O_MNK_-space]

#### 方法1：DFS（TLE） ####

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

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));
        }
    }

#### 方法2：BFS（AC） ####

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<int[]> 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;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

[https_leetcode.com_problems_shortest-path-in-a-grid-with-obstacles-elimination]: https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/e7a35507d50f4ac98c7d890f7f639d21.png
[Java-Straightforward-BFS-O_MNK_-time-or-O_MNK_-space]: https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/discuss/451796/Java-Straightforward-BFS-O%28MNK%29-time-or-O%28MNK%29-space
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/053a815b0a3446ada111843103136d8f.png