โปรแกรม C++ หาจำนวนเซลล์ที่ต้องบล็อกเพื่อสร้างเส้นทางเดียวในกริด

กริด h×w มีหุ่นยนต์ที่ (0,0) ต้องไป (h-1,w-1) เซลล์เป็น # (บล็อก) หรือ . (ทาง) หุ่นยนต์เดิน 4 ทิศทาง แต่อาจเดินวนรอบได้ ต้องบล็อกเซลล์ที่ไม่อยู่บนเส้นทางที่เลือก ให้เหลือเพียงเส้นทางเดียว หาจำนวนเซลล์ที่ต้องบล็อกเพิ่ม (ถ้าไม่มีทางเลย คืน -1)

ตัวอย่าง: h=4,w=4, grid={"..#.", "#.#.", "#.##", "#..."} ผลลัพธ์: 2 (บล็อก 2 เซลล์ ได้เส้นทางเดียว)

ขั้นตอนการแก้ปัญหา (BFS หา shortest path)

1. BFS จาก (0,0) หา distance ไปทุกเซลล์ (เฉพาะ .)
2. ถ้า distance[h-1][w-1] == INF คืน -1
3. นับเซลล์ . ทั้งหมด = count
4. ความยาวเส้นทางสั้นที่สุด = distance[h-1][w-1] + 1 (รวมจุดเริ่มต้น)
5. คำตอบ = count - (distance[h-1][w-1] + 1) (เซลล์ที่ไม่อยู่บนเส้นทางสั้นที่สุด)

ตัวอย่างโค้ด 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>> moves = {{-1,0},{1,0},{0,-1},{0,1}};
    queue<pair<int,int>> q;
    q.push({0,0});
    while (!q.empty()) {
        auto p = q.front(); q.pop();
        for (int i = 0; i < 4; i++) {
            int row = p.first + moves[i].first;
            int col = p.second + moves[i].second;
            if (row < 0 || row >= h || col < 0 || col >= w) continue;
            if (grid[row][col] == '#') continue;
            if (dp[p.first][p.second] + 1 < dp[row][col]) {
                dp[row][col] = dp[p.first][p.second] + 1;
                q.push({row, col});
            }
        }
    }
    if (dp[h-1][w-1] == 2500) return -1;
    int count = 0;
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            if (grid[i][j] == '.') count++;
    return count - (dp[h-1][w-1] + 1);
}

int main() {
    int h = 4, w = 4;
    vector<string> grid = {"..#.", "#.#.", "#.##", "#..."};
    cout << solve(h, w, grid);
    return 0;
}

อินพุต / เอาต์พุต

Input: 4, 4, {"..#.", "#.#.", "#.##", "#..."}

Output: 2