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 in one step.

Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.

&nbsp;
Example 1:

Input: grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1
Output: 6
Explanation: 
The shortest path without eliminating any obstacle is 10.
The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -&gt; (0,1) -&gt; (0,2) -&gt; (1,2) -&gt; (2,2) -&gt; (3,2) -&gt; (4,2).


Example 2:

Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1
Output: -1
Explanation: We need to eliminate at least two obstacles to find such a walk.


&nbsp;
Constraints:


	m == grid.length
	n == grid[i].length
	1 &lt;= m, n &lt;= 40
	1 &lt;= k &lt;= m * n
	grid[i][j] is either 0 or 1.
	grid[0][0] == grid[m - 1][n - 1] == 0


class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        Q = [[0, 0, k]] # m, n, remaining elimination quota 
        rows, cols = len(grid), len(grid[0])
        V, counter = {(0, 0):k}, 0 # I use a V to keep track of how cells have been visited
        
        while Q: 
            frontier = []
            for m, n, rem in Q: 
                if m == rows - 1 and n == cols - 1: 
                    return counter 
                for dm, dn in [[1, 0], [-1, 0], [0, 1], [0, -1]]: 
                    if 0 <= m+dm < rows and 0 <= n+dn < cols: # check inbound 
                        if grid[m+dm][n+dn] == 0: 
                            if (m+dm, n+dn) not in V or V[(m+dm, n+dn)] < rem: # if not visited or could be visited with fewer elimination 
                                frontier.append([m+dm, n+dn, rem])
                                V[(m+dm, n+dn)] = rem
                        elif rem > 0: # I see a wall and I can still eliminate
                            if (m+dm, n+dn) not in V or V[(m+dm, n+dn)] < rem - 1: # if not visited or could be visited with fewer elimination 
                                frontier.append([m+dm, n+dn, rem-1])
                                V[(m+dm, n+dn)] = rem - 1
            Q = frontier 
            counter += 1
                
        return -1
	```
class Solution {
    int rowLen = 0;
    int colLen = 0;
    int MAXVAL = 0;
    public int shortestPath(int[][] grid, int k) {
        rowLen = grid.length;
        colLen = grid[0].length;
        MAXVAL = rowLen * colLen + 1;
        int path = shortest(grid, k, 0, 0, 0, new boolean[rowLen][colLen], new Integer[rowLen][colLen][k+1][4]);
        return path == MAXVAL ? -1 : path;
    }

    /* Direction
    0 - Up
    1 - Down
    2 - Left
    3 - Right
    */

    // For each cell(row, col) explore all possible ways to reach it with minimum cost, hence we consider the direction as well
    int shortest(int[][] grid, int k, int row, int col, int direction, boolean[][] visited, Integer[][][][] dp){
        // Reached end of the matrix
        if(row == rowLen - 1 && col == colLen - 1 && k >= 0)
            return 0;

        // Couldn't find a valid path
        if(k < 0 || row < 0 || col < 0 || row >= rowLen || col >= colLen)
            return MAXVAL;

        if(dp[row][col][k][direction] != null)
            return dp[row][col][k][direction];

        // 4 options to choose a direction
        // Go right
        int op1 = MAXVAL;
        if(col + 1 < colLen && !visited[row][col+1]) {
            visited[row][col+1] = true;
            if(grid[row][col+1] == 0)
                op1 = shortest(grid, k, row, col+1, 3, visited, dp) + 1;
            else
                op1 = shortest(grid, k-1, row, col+1, 3, visited, dp) + 1;
            visited[row][col+1] = false;
        }

        // Go left
        int op2 = MAXVAL;
        if(col - 1 >= 0 && !visited[row][col-1]) {
            visited[row][col-1] = true;
            if(grid[row][col-1] == 0)
                op2 = shortest(grid, k, row, col-1, 2, visited, dp) + 1;
            else
                op2 = shortest(grid, k-1, row, col-1, 2, visited, dp) + 1;
            visited[row][col-1] = false;
        }

        // Go up
        int op3 = MAXVAL;
        if(row - 1 >= 0 && !visited[row-1][col]) {
            visited[row-1][col] = true;
            if(grid[row-1][col] == 0)
                op3 = shortest(grid, k, row-1, col, 0, visited, dp) + 1;
            else
                op3 = shortest(grid, k-1, row-1, col, 0, visited, dp) + 1;
            visited[row-1][col] = false;
        }

        // Go down
        int op4 = MAXVAL;
        if(row + 1 < rowLen && !visited[row+1][col]) {
            visited[row+1][col] = true;
            if(grid[row+1][col] == 0)
                op4 = shortest(grid, k, row+1, col, 1, visited, dp) + 1;
            else
                op4 = shortest(grid, k-1, row+1, col, 1, visited, dp) + 1;
            visited[row+1][col] = false;
        }

        dp[row][col][k][direction] = Math.min(Math.min(op1, op2), Math.min(op3, op4));
        return dp[row][col][k][direction];
    }
}
class Solution {
public:
    vector<vector<int>> directions{{-1,0},{1,0},{0,1},{0,-1}};
    int shortestPath(vector<vector<int>>& grid, int k) {
        int m = grid.size(),n = grid[0].size(),ans=0;
        queue<vector<int>> q;
        bool visited[m][n][k+1];
        memset(visited,false,sizeof(visited));
        q.push({0,0,k});
        visited[0][0][k]=true;
        
        while(!q.empty()) {
            int size = q.size();
            while(size--) {
                auto p = q.front();
                q.pop();
                
                if(p[0]==m-1 && p[1]==n-1) return ans;
                for(auto x : directions) {
                    int i= p[0]+x[0];
                    int j= p[1]+x[1];
                    int obstacle = p[2];
                    
                    if(i>=0 && i<m && j>=0 && j<n) {
                      if(grid[i][j]==0 && !visited[i][j][obstacle])  {
                          q.push({i,j,obstacle});
                          visited[i][j][obstacle] =true;
                      } else if(grid[i][j]==1 && obstacle>0 && !visited[i][j][obstacle-1]) {
                          q.push({i,j,obstacle-1});
                          visited[i][j][obstacle-1]=true;
                      }
                    } 
                }
            }
            ans++;
        }
        return -1;
    }
};
var shortestPath = function(grid, k) {
    const dir = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    const m = grid.length;
    const n = grid[0].length;
         
    let q = [[0,0,k]];
    const visited = new Set();
    visited.add(`0:0:${k}`);
    let cnt = 0;
    while(q.length>0)
    {
        const size  = q.length;
        for(let i = 0; i<size; i++)
        {
            let [x, y, ob] = q.shift();
            if(x === m-1 && y === n-1) {
                return cnt;
            }
            for(const d of dir)
            {
                const xx = d[0] + x;
                const yy = d[1] + y;
                if(xx>=0 && xx<m && yy>=0 && yy<n)
                {
                    const newK = grid[xx][yy] === 1 ? ob-1 : ob;
                    if(newK >=0 && !visited.has(`${xx}:${yy}:${newK}`) )
                    {
                        q.push([xx, yy, newK]);
                        visited.add(`${xx}:${yy}:${newK}`);
                    }
                }
            }
        }
        cnt++;
    }
    return -1;
};
Shortest Path in a Grid with Obstacles Elimination