给你一个 m * n 的网格,其中每个单元格不是 0(空)就是 1(障碍物)。每一步,您都可以在空白单元格中上、下、左、右移动。
如果您 最多 可以消除 k 个障碍物,请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径,并返回通过该路径所需的步数。如果找不到这样的路径,则返回 -1。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/shortest-path-in-a-grid-with-obstacles-elimination
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
深度优先搜索 + 记忆化(错误)
dp数组存储的不一定是最优值
import java.util.Arrays;
class Solution {
private static final int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
private int[][][] dp;
private int[][] grid;
private boolean[][] visited;
private int solve(int x, int y, int k) {
if (dp[x][y][k] == -1) {
if (grid[x][y] == 1 && k == 0) {
dp[x][y][k] = Integer.MAX_VALUE;
return Integer.MAX_VALUE;
}
if (x == grid.length - 1 && y == grid[0].length - 1) {
dp[x][y][k] = 0;
return 0;
}
if (grid[x][y] == 1) {
k--;
}
int ans = Integer.MAX_VALUE;
for (int i = 0; i < directions.length; ++i) {
int nx = x + directions[i][0];
int ny = y + directions[i][1];
if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length && !visited[nx][ny]) {
visited[nx][ny] = true;
ans = Math.min(ans, solve(nx, ny, k));
visited[nx][ny] = false;
}
}
dp[x][y][k] = ans == Integer.MAX_VALUE ? ans : ans + 1;
}
return dp[x][y][k];
}
public int shortestPath(int[][] grid, int k) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
this.grid = grid;
this.visited = new boolean[grid.length][grid[0].length];
this.dp = new int[grid.length][grid[0].length][k + 1];
for (int i = 0; i < grid.length; ++i) {
for (int j = 0; j < grid[0].length; ++j) {
Arrays.fill(dp[i][j], -1);
}
}
visited[0][0] = true;
int ans = solve(0, 0, k);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
}
广度优先搜索
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
class Solution {
private static final int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
public int shortestPath(int[][] grid, int k) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int m = grid.length, n = grid[0].length;
if (m == 1 && n == 1) {
return 0;
}
k = Math.min(m + n - 3, k);
boolean[][][] visited = new boolean[m][n][k + 1];
visited[0][0][k] = true;
Queue<Info> queue = new LinkedList<>();
queue.offer(new Info(0, 0, 0, k));
while (!queue.isEmpty()) {
Info node = queue.poll();
if (node.x == m - 1 && node.y == n - 1) {
return node.step;
}
for (int i = 0; i < directions.length; ++i) {
int nx = node.x + directions[i][0];
int ny = node.y + directions[i][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
if (grid[nx][ny] == 1) {
if (node.k > 0 && !visited[nx][ny][node.k - 1]) {
visited[nx][ny][node.k - 1] = true;
queue.offer(new Info(nx, ny, node.step + 1, node.k - 1));
}
} else {
if (!visited[nx][ny][node.k]) {
visited[nx][ny][node.k] = true;
queue.offer(new Info(nx, ny, node.step + 1, node.k));
}
}
}
}
}
return -1;
}
public static void main(String[] args) {
int[][] grid = {{0}};
int k = 2;
System.out.println(new Solution().shortestPath(grid, k));
}
}
class Info {
int x;
int y;
int step;
int k;
public Info(int x, int y, int step, int k) {
this.x = x;
this.y = y;
this.step = step;
this.k = k;
}
}