###### tags: `LeetCode`

# #1293 Shortest Path in a Grid with Obstacles Elimination

Difficulty : <span style="color: red">**HARD**</span>

# Description

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`.

# Example Inputs and Outputs

## Example 1

:::spoiler Picture
:::

</br>

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) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).

## Example 2

:::spoiler Picture
:::

</br>

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.

# 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

# Related Topics

* **Array**
* **Breadth-First Search**
* **Matrix**

# Reference Solution

## Ver. 1 _ Optimization

### Explanations and Ideas

*IDEAS*

If it is not allowed to cross the obstacle, then we can use the usual BFS practice to record the shortest number of steps `dp[i][j]` required to reach each position (i, j). But now it is allowed to cross the obstacle and reach ( The minimum number of steps for i, j ) should be differentiated.

Here is an example

O X O O O
O X O O O
O O O O O

In the example above, it would take 6 steps to go from `(0,0)` to `(0,2)` if the obstacle is not to be crossed. But if the obstacle is allowed to be crossed, then only 2 steps are required. So which one is better to choose ? The answer is no way. The former uses fewer eleminations ( which can be reserved for later steps ), and the latter has fewer actual steps. So we have to record these two states. Therefore, we use `dp[i][j][k]` to represent the shortest number of steps required to go from `(0,0)` to `(i,j)` and use `k` obstacle eliminations.

Because this problem is allowed to move up, down, left and right, there is no "no aftereffect", so `dp[i][j][k]` cannot be transferred using dynamic programming, and can only be moved forward by the brute force search of BFS. For example, we know that `dp[i][j][k] = step`, then if we take one step to the right to the open space, we have `dp[i][j+1][k] = step+1`; but pay special attention if If one step to the right is an obstacle, then you need to use an obstacle elimination, that is `dp[i][j+1][k+1] = step+1`.

### Code

:::spoiler Code in Leetcode _ Ver. 1 _ Optimization

class Solution {
    bool visited[45][45][1650];
public:
    int shortestPath(vector<vector<int>>& grid, int K) {
        int m = grid.size();    // for high
        int n = grid[0].size(); // for wide
        
        queue <vector<int>> q;
        q.push({0, 0, 0});
        visited[0][0][0] = 1;
        auto dir = vector<pair<int,int>> ( { {1, 0}, {0, 1}, {-1, 0}, {0, -1} } );
        
        if( m == 1 && n == 1 ) return 0;
        
        int step = 0;
        while( !q.empty() ){
            int len = q.size();
            while( len-- ){
                int x = q.front()[0];
                int y = q.front()[1];
                int k = q.front()[2];
                q.pop();
                
                for( int t = 0 ; t < 4 ; t++ ){
                    int i = x + dir[t].first;
                    int j = y + dir[t].second;
                    
                    if( i < 0 || i >= m || j < 0 || j >= n ) continue;
                    if( i == m - 1 && j == n - 1 ) return step + 1;
                    
                    if( grid[i][j] == 1 ){
                        if( k == K ) continue;
                        if( visited[i][j][k+1] ) continue;
                        visited[i][j][k+1] = 1;
                        q.push({i, j, k+1});
                    }
                    else{
                        if( visited[i][j][k] ) continue;
                        visited[i][j][k] = 1;
                        q.push({i, j, k});
                    }
                }
            }
            step += 1;
        }
        return -1;
    }
}; 

:::

# Related Links

* [Shortest Path in a Grid with Obstacles Elimination](https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/)
* [Youtube - Huifeng Guan - 55. Jump Game, 9/28/2020](https://youtu.be/2pLhH2eLaP8)
* [My Problem Solving Process on Youtube](https://youtu.be/xVO9c-2nEKE)