[Hard] 1293. Shortest Path in a Grid with Obstacles Elimination (Java)
https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/description/
Shortest Path in a Grid with Obstacles Elimination - LeetCode
Can you solve this real interview question? Shortest Path in a Grid with Obstacles Elimination - You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell
leetcode.com
Very hard..?
※ Question Summary
▶ There is m x n Integer array grid where each value has 0(empty) or 1(obstacle)
▶ You can move up, down, left, right from and to an empty cell in one step
▶ You can eliminate at most k obstacles
▶ Return the minimum number of steps to walk from the (0,0) to (m-1, n-1)
▶ if it's not possible to find such walk return -1
◈ Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 40
- 1 <= k <= m * n
- grid[i][j] is either 0 or 1.
- grid[0][0] == grid[m - 1][n - 1] == 0
◈ Input - 1
grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1◈ Output - 1
6◈ Input - 2
grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1◈ Output - 2
-1◎ Solution 1 ( failed - time limit exceed )
▶ Create the class 'Point' which has the row and the col and the count of steps
▶ Initialize the result as '-1' to return -1 if there is no way to get last point
▶ Create the function perm to check every case for eliminating obstacles
▶ Create the 2d array 'visit' to check if it's visited
▶ do the BFS for searching the way to get last point
◈ Last Executed Input
[[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]
k=5class Point {
int m_nRow;
int m_nCol;
int m_nCount;
Point(int nRow, int nCol, int nCount) {
m_nRow = nRow;
m_nCol = nCol;
m_nCount = nCount;
}
}
class Solution {
int[] narrStacks;
int[][] narrGrid;
boolean[] barrStacks;
ArrayList<Point> listObstacles;
int nSteps;
int K;
public int shortestPath(int[][] grid, int k) {
nSteps = Integer.MAX_VALUE;
listObstacles = new ArrayList<>();
// find the obstacles and copy the array
narrGrid = new int[grid.length][grid[0].length];
for(int i = 0 ; i < grid.length; i++) {
for(int j = 0 ; j < grid[i].length; j++) {
if(grid[i][j] == 1)
listObstacles.add(new Point(i, j, 0));
narrGrid[i][j] = grid[i][j];
}
}
K = 0;
while(K <= k) {
narrStacks = new int[K];
barrStacks = new boolean[listObstacles.size()];
perm(0);
K++;
}
if(nSteps == Integer.MAX_VALUE)
return -1;
return nSteps;
}
public void perm(int nIndex) {
if(nIndex == K){
// eliminate K obstacles
for(int i = 0; i < K; i++) {
int nRow = listObstacles.get(narrStacks[i]).m_nRow;
int nCol = listObstacles.get(narrStacks[i]).m_nCol;
narrGrid[nRow][nCol] = 0;
}
BFS();
// repair K obstacles since it's checked
for(int i = 0; i < K; i++) {
int nRow = listObstacles.get(narrStacks[i]).m_nRow;
int nCol = listObstacles.get(narrStacks[i]).m_nCol;
narrGrid[nRow][nCol] = 1;
}
return;
}
//
for(int i = 0; i < listObstacles.size(); i++) {
// ex) 0,1 == 1,0 so i don't have to search twice
if(nIndex > 0 && narrStacks[nIndex-1] > i)
continue;
if(!barrStacks[i]) {
narrStacks[nIndex] = i;
barrStacks[i] = true;
perm(nIndex+1);
barrStacks[i] = false;
}
}
}
public void BFS() {
// Search Dircetion
int[] dr = {0, 0, 1, -1};
int[] dc = {1, -1, 0, 0};
boolean[][] barrVisit = new boolean[narrGrid.length][narrGrid[0].length];
Queue<Point> BFS = new LinkedList<>();
BFS.add(new Point(0,0,0));
while(!BFS.isEmpty()) {
Point p = BFS.poll();
if(barrVisit[p.m_nRow][p.m_nCol])
continue;
if(p.m_nRow == narrGrid.length-1 && p.m_nCol == narrGrid[0].length -1){
if(nSteps > p.m_nCount)
nSteps = p.m_nCount;
return;
}
barrVisit[p.m_nRow][p.m_nCol] = true;
for(int i = 0; i < dr.length; i++) {
int nRow = p.m_nRow + dr[i];
int nCol = p.m_nCol + dc[i];
if(nRow < 0 || nCol < 0 || nRow >= narrGrid.length || nCol >= narrGrid[0].length)
continue;
if(barrVisit[nRow][nCol] || narrGrid[nRow][nCol] == 1)
continue;
BFS.add(new Point(nRow, nCol, p.m_nCount +1));
}
}
}
}◎ Solution 2 ( Accepted )
▶ Create the class 'Point' which has the row and the col and the count of steps, count of elimination
▶ Initialize the result as '-1' to return -1 if there is no way to get last point
▶ Delete the function perm
▶ Create the 3d array 'visit' to check if it's visited with the row,col and the count of eliminate
( since it needs to be checked in every situation when eliminating obstacles )
▶ do the BFS for searching the way to get last point
▶ Return the count of steps when the first time get the point(m-1, n-1) since it means the shortest way
class Point {
int m_nRow;
int m_nCol;
int m_nSteps;
int m_nEliminate;
Point(int nRow, int nCol, int nSteps, int nEliminate) {
m_nRow = nRow;
m_nCol = nCol;
m_nSteps = nSteps;
m_nEliminate = nEliminate;
}
}
class Solution {
int[][] narrGrid;
int nSteps;
int K;
public int shortestPath(int[][] grid, int k) {
nSteps = Integer.MAX_VALUE;
// copy the array
narrGrid = new int[grid.length][grid[0].length];
for(int i = 0 ; i < grid.length; i++) {
for(int j = 0 ; j < grid[i].length; j++) {
narrGrid[i][j] = grid[i][j];
}
}
K = k;
BFS();
if(nSteps == Integer.MAX_VALUE)
return -1;
return nSteps;
}
public void BFS() {
// Search Dircetion
int[] dr = {0, 0, 1, -1};
int[] dc = {1, -1, 0, 0};
boolean[][][] barrVisit = new boolean[narrGrid.length][narrGrid[0].length][K+1];
Queue<Point> BFS = new LinkedList<>();
BFS.add(new Point(0,0,0,0));
barrVisit[0][0][0] = true;
while(!BFS.isEmpty()) {
Point p = BFS.poll();
if(p.m_nRow == narrGrid.length-1 && p.m_nCol == narrGrid[0].length -1){
if(nSteps > p.m_nSteps)
nSteps = p.m_nSteps;
return;
}
for(int i = 0; i < dr.length; i++) {
int nRow = p.m_nRow + dr[i];
int nCol = p.m_nCol + dc[i];
if(nRow < 0 || nCol < 0 || nRow >= narrGrid.length || nCol >= narrGrid[0].length)
continue;
int eliminate = p.m_nEliminate + narrGrid[nRow][nCol];
if (eliminate > K || barrVisit[nRow][nCol][eliminate])
continue;
barrVisit[nRow][nCol][eliminate] = true;
BFS.add(new Point(nRow, nCol, p.m_nSteps + 1, eliminate));
}
}
}
}I HOPE YOUR DAY GOES WELL :)