tags: `LeetCode`

#1293 Shortest Path in a Grid with Obstacles Elimination

Difficulty : HARD

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

Picture

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

Picture

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

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

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;
    }
};

tags: LeetCode