Here is the problem link for reference: - LeetCode
int shortestPath(vector<vector<int>>& grid, int k) {
int n = grid.size();
int m = grid[0].size();
priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>> pq;
vector<vector<vector<int>>> distTo(n,vector<vector<int>> (m,vector<int> (k+1,INT_MAX)));
for(int i=0;i<=k;i++){
distTo[0][0][i] = 0;
}
//pq ({dist,nodeX,nodeY,eliminations})
pq.push({0,0,0,0});
while(!pq.empty()){
vector<int> it = pq.top();
int dist = it[0];
int nodeX = it[1];
int nodeY = it[2];
int eliminated = it[3];
pq.pop();
if(distTo[nodeX][nodeY][eliminated] < dist) continue;
for(int i=0;i<4;i++){
int newX = nodeX + dx[i];
int newY = nodeY + dy[i];
if(!isValid(newX,newY,n,m)) continue;
if(grid[newX][newY] == 0){
if(distTo[newX][newY][eliminated] > distTo[nodeX][nodeY][eliminated] + 1){
distTo[newX][newY][eliminated] = distTo[nodeX][nodeY][eliminated] + 1;
pq.push({distTo[newX][newY][eliminated],newX,newY,eliminated});
}
}else{
if(eliminated == k) continue;
if(distTo[newX][newY][eliminated+1] > distTo[nodeX][nodeY][eliminated] + 1){
distTo[newX][newY][eliminated+1] = distTo[nodeX][nodeY][eliminated] + 1;
pq.push({distTo[newX][newY][eliminated+1],newX,newY,eliminated+1});
}
}
}
}