Đường đi ngắn nhất trong lưới với loại bỏ chướng ngại vật trong C++

Cho lưới m x n, ô 0 trống, 1 chặn. Di chuyển 4 hướng trên ô trống. Tìm số bước tối thiểu từ (0,0) đến (m-1,n-1) có thể loại bỏ tối đa k chướng ngại. Trả về -1 nếu không thể.

Ví dụ: lưới 5x3, k=1. Đường ngắn nhất không loại bỏ: 10. Loại bỏ chướng ngại tại (3,2): 6 bước. Đường: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)→(3,2)→(4,2).

Giải pháp

BFS 3D với trạng thái (x, y, k_remaining):

• dp[x][y][k] = độ dài ngắn nhất đến (x,y) với k chướng ngại còn lại
• Khởi tạo dp = INF, queue từ (0,0,k,0)
• While queue không rỗng:
  • Lấy node, nếu đến đích → trả về length
  • Thử 4 hướng: nx, ny
  • Nếu ô trống (0) và length < dp[nx][ny][k]: push, cập nhật dp
  • Nếu ô chặn (1) và k>0 và length < dp[nx][ny][k]: push với k-1, cập nhật dp
• Trả về -1 nếu hết queue

Ví dụ mã C++

#include <bits/stdc++.h> 
using namespace std; 

int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; 
int dp[50][50][2000]; 

struct Data { 
    int x, y, k, length; 
    Data(int a, int b, int c, int d) { x=a; y=b; k=c; length=d; } 
}; 

class Solution { 
public: 
    void pre() { 
        for (int i = 0; i < 50; i++) 
            for (int j = 0; j < 50; j++) 
                for (int k = 0; k < 2000; k++) 
                    dp[i][j][k] = INT_MAX; 
    } 
    
    bool ok(int x, int y, int r, int c) { 
        return (x < r && y < c && x >= 0 && y >= 0); 
    } 
    
    int shortestPath(vector<vector<int> >& grid, int k) { 
        pre(); 
        int r = grid.size(); 
        int c = grid[0].size(); 
        queue<Data> q; 
        Data root(0, 0, k, 0); 
        q.push(root); 
        
        while (!q.empty()) { 
            Data node = q.front(); q.pop(); 
            int x = node.x, y = node.y, k = node.k, length = node.length; 
            
            if (x == r-1 && y == c-1) return length; 
            length++; 
            
            for (int i = 0; i < 4; i++) { 
                int nx = x + dir[i][0]; 
                int ny = y + dir[i][1]; 
                if (nx == r-1 && ny == c-1) return length; 
                if (ok(nx, ny, r, c)) { 
                    if (grid[nx][ny] == 0) { 
                        if (length < dp[nx][ny][k]) { 
                            q.push(Data(nx, ny, k, length)); 
                            dp[nx][ny][k] = length; 
                        } 
                    } else { 
                        if (k > 0 && length < dp[nx][ny][k]) { 
                            q.push(Data(nx, ny, k-1, length)); 
                            dp[nx][ny][k] = length; 
                        } 
                    } 
                } 
            } 
        } 
        return -1; 
    } 
}; 

int main() { 
    Solution ob; 
    vector<vector<int>> v = {{0,0,0},{1,1,0},{0,0,0},{0,1,1},{0,0,0}}; 
    cout << (ob.shortestPath(v, 1)); 
    return 0; 
}

Đầu vào

{{0,0,0},{1,1,0},{0,0,0},{0,1,1},{0,0,0}}

Đầu ra

6