leetcode 1293. Shortest Path in a Grid with Obstacles Elimination

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

本文主要是介绍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

方法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 stepspublic 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;}
}