1293. Shortest Path in a Grid with Obstacles Elimination
add one more dimension in visited
[x][y]k+1]: ่จ้ๅจๆๅบงๆจ, ็ฌฌไธ็ถญ็ด้ ไฝฟ็จ็ๆถ้คๆฌกๆธ 0~k ๏ผboolean
so
็ถๅพๅๆ้็ค็ๅบงๆจๅๆฒ้็ค็ๅบงๆจๅป่็
if (grid[x][y] == 1)
elseๅ้ๅฐๆ้็ค็ๅบงๆจๆ, ้ๆจฃไปฃ่กจ็จๅฎไบ
if (k == obs || visited[x][y][k+1])
k == obs, ไปฃ่กจ ๆถ้คๆฌกๆธ็จๅฐ k ๆฌกไบ, ไธ่ฝๅ็จ
visited[x][y][k+1] ไปฃ่กจๅจ้ๅบงๆจไธ ๆถ้คๆฌกๆธ็็ๆ
๏ผtrue, ไปฃ่กจ kๆฌกๆถ้คๆฌกๆธๅจ้ๅบงๆจ็จไบ
in next queue poll, we can get from previous xy ๅบงๆจๅ ็จไบๅนพๆฌกๆถ้คๆฌกๆธ๏ผk)
T: O(mnk) , mn is the be the number of cells in the grid, and K be the quota to eliminate obstacles.
S: O(mnk)
class Solution {
private int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
public int shortestPath(int[][] grid, int obs) {
int m = grid.length;
int n = grid[0].length;
// ๆณจๆ visited ็ๆ
ๅฏไปฅ้ๆจฃๅฏซ, ๅคไธๅ "ไฝฟ็จ็ๆถ้ค้็คๆธ"
boolean visited[][][] = new boolean[m][n][obs+1]; // obs: 0~obs => obs+1
Queue<int[]> queue = new ArrayDeque<>();
queue.offer(new int[]{0,0,0});
visited[0][0][0] = true;
int steps = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] curr = queue.poll();
int currX = curr[0];
int currY = curr[1];
int k = curr[2];
// ๅฏซๅจๅค้ข็ๅช้ปๆฏ, ็ถๅชๆไธๅ data ๆ, ้้ๆฏๅฏไปฅ่ฟๅ็, ๅฏซๅจๅ
งๅฑค็กๆณ, ่ฆ็นๅฅ่็
if (currX == m - 1 && currY == n - 1) {
return steps;
}
for (int dir[] : dirs) {
int x = currX + dir[0];
int y = currY + dir[1];
if (!isInArea(grid, x, y)) {
continue;
}
if (grid[x][y] == 1) { // ๅฆๆๆฏ้็ค, ้่ฆ็จๆถ้ค้็ค, ๆ่ฝ็นผ็บๅ ๅฐ queue bfs
if (k == obs || visited[x][y][k+1]) { // k == obs, ๅทฒ็ถ็จๅฎๆถ้ค้็ค็
continue;
}
queue.offer(new int[]{x, y, k+1}); // ๆถ้ค้็คๆธ็ฎ+1
visited[x][y][k+1] = true;
} else { // ้้็ค, ๆญฃๅธธ่็
if (visited[x][y][k]) {
continue;
}
queue.offer(new int[]{x, y, k});
visited[x][y][k] = true;
}
}
}
steps++;
}
return -1;
}
private boolean isInArea(int[][] grid, int i, int j) {
return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length;
}
}
/*
T: O(mnk)
S: O(mnk)
define
visited[i][j][k]
if (next 4 dir + (i,j)) == 1)
if k == K continue;
visited[new i][new j][k+1]
if (next 4 dir + (i,j)) == 0)
visited[new i][new j][k]
*/simpler version
class Solution {
private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public int shortestPath(int[][] grid, int k) {
int m = grid.length;
int n = grid[0].length;
boolean[][][] visited = new boolean[m][n][k+1];
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{0, 0, 0});
visited[0][0][0] = true;
int steps = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] cur = queue.poll();
int curX = cur[0];
int curY = cur[1];
int curObs = cur[2];
if (curX == m - 1 && curY == n - 1) {
return steps;
}
for (int[] dir : DIRS) {
int x = dir[0] + curX;
int y = dir[1] + curY;
// alert!! this curObs must assign to a new variable(obs),
// or it will be wrong!!!
int obs = curObs;
if (!isValid(grid, x, y)) {
continue;
}
if (grid[x][y] == 1) {
obs++;
}
if (obs > k || visited[x][y][obs]) {
continue;
}
queue.offer(new int[] {x, y, obs});
visited[x][y][obs] = true;
}
}
steps++;
}
return -1;
}
private boolean isValid(int[][] grid, int x, int y) {
int m = grid.length;
int n = grid[0].length;
return x >= 0 && x < m && y >= 0 && y < n;
}
}print with path
class Solution {
private static final int[][] DIRS = {{1,0}, {-1,0}, {0,1}, {0,-1}};
private static final String[] DIRSTR = {"d", "u", "r", "l"}; // row col base
class Data {
int x;
int y;
int obs;
String path;
Data (int x, int y, int obs, String path) {
this.x = x;
this.y = y;
this.obs = obs;
this.path = path;
}
}
public int shortestPath(int[][] grid, int k) {
int m = grid.length;
int n = grid[0].length;
boolean[][][] visited = new boolean[m][n][k+1]; // k+1 !
Queue<Data> queue = new LinkedList<>();
queue.offer(new Data(0 , 0, 0, ""));
visited[0][0][0] = true;
int steps = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int q = 0; q < size; q++) {
Data cur = queue.poll();
int curX = cur.x;
int curY = cur.y;
int curObs = cur.obs;
String curPath = cur.path;
if (curX == m - 1 && curY == n - 1) {
System.out.println("final path:" + curPath);
return steps;
}
for (int i = 0; i < 4; i++) {
int x = curX + DIRS[i][0];
int y = curY + DIRS[i][1];
int obs = curObs;
String path = curPath + DIRSTR[i];
if (!isValid(m, n, x, y)) {
continue;
}
if (grid[x][y] == 1) {
obs++;
}
if (obs > k || visited[x][y][obs]) {
continue;
}
queue.offer(new Data(x , y, obs, path));
visited[x][y][obs] = true;
}
}
steps++;
}
return -1;
}
private boolean isValid(int m, int n, int x, int y) {
return x >= 0 && x < m && y >= 0 && y < n;
}
}
/*
weight is 1
BFS
you can eliminate at most k obstacles => use one more dim to record eliminatation times <= k
Queue<int[]> => int[x][y][k]
start from 0,0 end to m-1, n-1
T: O(mnk)
S: O(mnk)
*/shorter version
class Solution {
private static final int[][] DIRS = {{0,1}, {1,0}, {0,-1}, {-1,0}};
public int shortestPath(int[][] grid, int k) {
int m = grid.length;
int n = grid[0].length;
boolean[][][] visited = new boolean[m][n][k+1]; // 0~k obs
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{0 , 0, 0});
visited[0][0][0] = true;
int steps = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] cur = queue.poll();
if (cur[0] == m-1 && cur[1] == n - 1) {
return steps;
}
for (int[] dir : DIRS) {
int x = cur[0] + dir[0];
int y = cur[1] + dir[1];
int toolUsedCount = cur[2];
if (!inArea(grid, x, y)) {
continue;
}
if (grid[x][y] == 1) { // if is obstacle, use tool to eliminate
toolUsedCount++;
}
if (toolUsedCount > k || visited[x][y][toolUsedCount]) {
continue;
}
queue.offer(new int[]{x, y, toolUsedCount});
visited[x][y][toolUsedCount] = true;
}
}
steps++;
}
return -1;
}
private boolean inArea(int[][] grid, int x, int y) {
return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
}
}
/*
010
000
010
*/new version
```java
class Solution {
private int[][] DIRECTIONS = {{0,1}, {1,0}, {0,-1}, {-1,0}};
class Step {
int x;
int y;
int level;
int removeCount;
Step(int x, int y, int level, int removeCount) {
this.x = x;
this.y = y;
this.level = level;
this.removeCount = removeCount;
}
}
public int shortestPath(int[][] grid, int k) {
int m = grid.length;
int n = grid[0].length;
Queue<Step> queue = new LinkedList<>();
queue.offer(new Step(0, 0, 0, 0));
boolean[][][] visited = new boolean[m][n][k+1];
while (!queue.isEmpty()) {
Step cur = queue.poll();
if (!inArea(grid, cur.x, cur.y) || visited[cur.x][cur.y][cur.removeCount]) {
continue;
}
if (cur.x == m-1 && cur.y == n-1) {
return cur.level;
}
visited[cur.x][cur.y][cur.removeCount] = true;
for (int[] dir : DIRECTIONS) {
int x = cur.x + dir[0];
int y = cur.y + dir[1];
int count = cur.removeCount;
if (inArea(grid, x, y) && grid[x][y] == 1) {
count++;
}
if (count > k) {
continue;
}
queue.offer(new Step(x, y, cur.level+1, count));
}
}
return -1;
}
private boolean inArea(int[][] grid, int x, int y) {
int m = grid.length;
int n = grid[0].length;
return x >= 0 && x < m && y >= 0 && y < n;
}
}
```More consistent way
or ...still check count first... all good
```java
class Solution {
private static final int[][] DIRECTIONS = {{1,0}, {0, 1}, {-1,0}, {0, -1}};
class Step {
int x;
int y;
int level;
int removedObstacles;
Step(int x, int y, int level, int removedObstacles) {
this.x = x;
this.y = y;
this.level = level;
this.removedObstacles = removedObstacles;
}
}
public int shortestPath(int[][] grid, int k) {
int m = grid.length;
int n = grid[0].length;
Queue<Step> queue = new LinkedList<>();
queue.offer(new Step(0, 0, 0, 0));
boolean[][][] visited = new boolean[m][n][k+1];
while (!queue.isEmpty()) {
Step cur = queue.poll();
// more consistent way
if (!inArea(grid, cur.x, cur.y) || cur.removedObstacles > k || visited[cur.x][cur.y][cur.removedObstacles]) {
continue;
}
visited[cur.x][cur.y][cur.removedObstacles] = true;
if (cur.x == m - 1 && cur.y == n-1) {
return cur.level;
}
for (int[] dir : DIRECTIONS) {
int nextX = cur.x + dir[0];
int nextY = cur.y + dir[1];
int count = cur.removedObstacles;
if (inArea(grid, nextX, nextY) && grid[nextX][nextY] == 1) {
count++;
}
queue.offer(new Step(nextX, nextY, cur.level + 1, count));
}
}
return -1;
}
private boolean inArea(int[][] grid, int x, int y) {
int m = grid.length;
int n = grid[0].length;
return x >= 0 && x < m && y >=0 && y < n;
}
}
```Last updated
