Chương trình C++ đếm ô cần chặn để tạo đường đi duy nhất trong lưới

Mô tả bài toán

Lưới h×w, robot từ (0,0) đến (h-1,w-1). Ô '.' = đi được, '#' = chặn. Robot đi 4 hướng. Phải chặn các ô không nằm trên đường đi để chỉ còn 1 đường đi duy nhất. Tìm số ô cần chặn thêm (trả -1 nếu không có đường).

Ví dụ

h=4,w=4, grid={"..#.", "#.#.", "#.##", "#..."}. Đầu ra: 2.

Thuật toán (BFS đường đi ngắn nhất)

1. BFS từ (0,0) tìm khoảng cách ngắn nhất dist đến mọi ô.
2. Nếu dist[h-1][w-1]==INF → trả -1.
3. Đếm tổng ô trống count. Số ô trên đường đi ngắn nhất = dist[h-1][w-1]+1.
4. Kết quả = count - (dist[h-1][w-1]+1).

Đoạn mã C++

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

int solve(int h,int w,vector<string> grid){
    vector<vector<int>> dp(h,vector<int>(w,2500));
    dp[0][0]=0;
    vector<pair<int,int>> mv={{-1,0},{1,0},{0,-1},{0,1}};
    queue<pair<int,int>> q;
    q.push({0,0});
    while(!q.empty()){
        auto [x,y]=q.front(); q.pop();
        for(auto [dx,dy]:mv){
            int nx=x+dx, ny=y+dy;
            if(nx<0||nx>=h||ny<0||ny>=w) continue;
            if(grid[nx][ny]=='#') continue;
            if(dp[x][y]+1 < dp[nx][ny]){
                dp[nx][ny]=dp[x][y]+1;
                q.push({nx,ny});
            }
        }
    }
    if(dp[h-1][w-1]==2500) return -1;
    int cnt=0;
    for(int i=0;i