เส้นทางสั้นที่สุดในกริดมีการกำจัดอุปสรรคใน C++

คำอธิบายโจทย์

กริด m×n ค่า 0=ว่าง 1=บล็อก เดิน 4 ทิศทาง ได้กำจัดอุปสรรคสูงสุด k ตัว หา steps น้อยสุดจาก (0,0) ถึง (m-1,n-1) ไม่ได้คืน -1

ตัวอย่าง

grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k=1 → Output: 6

กำจัดอุปสรรคที่ (3,2) ทำให้สั้นลงจาก 10 เป็น 6

วิธีแก้ปัญหา

BFS 3 มิติ State: (x, y, k_remaining)

dp[x][y][k] = steps น้อยสุดที่ถึง (x,y) เหลือ k
Queue เก็บ (x,y,k,length)
เดิน 4 ทิศทาง: ถ้า 0 → คง k, ถ้า 1 และ k>0 → k-1
อัปเดต dp ก็ต่อเมื่อ length น้อยกว่าที่บันทึกไว้
ถึงปลาย → คืน length

การทำงานของโค้ด

#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>=0 && y>=0 && x0 && len < dp[nx][ny][k]) {
                        q.push(Data(nx,ny,k-1,len));
                        dp[nx][ny][k]=len;
                    }
                }
            }
        }
        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;
}

อินพุต