贡献一题 Shortest Path Breaking Through Walls
Given a 2D grid of size r * c, where 1 is a wall (the cell is blocked) and 0 is empty (the cell to which you can travel). You have a hammer that you can use to break 1 wall. Is there a way to go from the upper left corner (0, 0) to the lower right corner (r - 1, c - 1)? If there is a way to go, find the length of the shortest path. You can move up, down, left or right at a time.
Example 1:
Input:
[[0, 1, 0, 0, 0],
[0, 0, 0, 1, 0],
[1, 1, 0, 1, 0],
[1, 1, 1, 1, 0]]
Output: 7
Explanation: Change 1 at (0, 1) to 0, the shortest path is as follows:
(0, 0) -> (0, 1) -> (0, 2) -> (0, 3) -> (0, 4) -> (1, 4) -> (2, 4) -> (3, 4)
There are other options of length 7, not listed here.
Example 2:
Input:
[[0, 1, 1],
[1, 1, 0],
[1, 1, 0]]
Output: -1
Explanation: Regardless of which 1 is changed to 0, there is no viable path.
You can assume (0, 0) and (r - 1, c - 1) are always empty.
Follow-up:
What if you can break k walls?
public class Main {
private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static void main(String[] args) {
int[][] grid = {
{0, 1, 0, 0, 0},
{0, 0, 0, 1, 0},
{1, 1, 0, 1, 0},
{1, 1, 1, 1, 0}};
System.out.println(minDist(grid, 1)); // 7
int[][] grid2 = {
{0, 1, 1},
{1, 1, 0},
{1, 1, 0}};
System.out.println(minDist(grid2, 1)); // -1
System.out.println(minDist(grid2, 2)); // 4
}
public static int minDist(int[][] grid, int k) {
int rows = grid.length;
int cols = grid[0].length;
Queue<Point> q = new ArrayDeque<>();
q.add(new Point(0, 0, 0));
boolean[][] visited = new boolean[rows][cols];
visited[0][0] = true;
for (int dist = 0; !q.isEmpty(); dist++) {
for (int sz = q.size(); sz > 0; sz--) {
Point p = q.poll();
if (p.r == rows - 1 && p.c == cols - 1) return dist;
for (int[] dir : DIRS) {
int r = p.r + dir[0];
int c = p.c + dir[1];
if (isSafe(grid, r, c, visited)) {
int brokenWalls = p.walls + grid[r][c];
if (brokenWalls <= k) {
visited[r][c] = true;
q.add(new Point(r, c, brokenWalls));
}
}
}
}
}
return -1;
}
private static boolean isSafe(int[][] grid, int r, int c, boolean[][] visited) {
return r >= 0 && r < grid.length && c >= 0 && c < grid[0].length && !visited[r][c];
}
private static class Point {
int r;
int c;
int walls; // number of broken wall on the path
public Point(int r, int c, int walls) {
this.r = r;
this.c = c;
this.walls = walls;
}
}
}
Time complexity: O(r *c) .
Space complexity: O(r *c) .