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

กำหนดกริดที่มีเซลล์ 2 ประเภท: สีดำ (#) และสีขาว (.) ในแต่ละรอบ จะเปลี่ยนเซลล์สีขาวที่ติดกับเซลล์สีดำ (แนวนอน/แนวตั้ง) ให้กลายเป็นสีดำ ทำซ้ำจนกว่าทุกเซลล์จะเป็นสีดำ ต้องการหาจำนวนรอบที่ใช้ (กริดเริ่มต้นต้องมีเซลล์ดำอย่างน้อย 1 เซลล์)

ตัวอย่าง: h = 4, w = 4, grid = {"#...", ".#..", "....", "...#"} ผลลัพธ์คือ 3 ใช้ 3 รอบในการเปลี่ยนทั้งหมดเป็นสีดำ

ขั้นตอนการแก้ปัญหา (BFS หลายแหล่งที่มา)

1. กำหนดทิศทาง 4 ด้าน: dx = {1,0,-1,0}, dy = {0,1,0,-1}
2. สร้างอาร์เรย์ distance เริ่มต้น -1 และคิว q
3. ใส่เซลล์สีดำทั้งหมดเข้าคิว พร้อมตั้ง distance = 0
4. BFS: ดึงเซลล์จากคิว ตรวจสอบ 4 ทิศทาง ถ้าเป็นเซลล์สีขาวและยังไม่ได้ไป (distance == -1) ตั้ง distance = distance[ปัจจุบัน] + 1 ใส่คิว
5. คำตอบคือค่า distance สูงสุดในกริด

ตัวอย่างโค้ด C++

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

void solve(int h, int w, vector<string> grid) {
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};
    vector<vector<int>> distance(h, vector<int>(w, -1));
    queue<pair<int, int>> q;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (grid[i][j] == '#') {
                distance[i][j] = 0;
                q.push({i, j});
            }
        }
    }
    while (!q.empty()) {
        auto now = q.front(); q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int cx = now.first + dx[dir];
            int cy = now.second + dy[dir];
            if (cx < 0 || cx >= h || cy < 0 || cy >= w) continue;
            if (distance[cx][cy] == -1) {
                distance[cx][cy] = distance[now.first][now.second] + 1;
                q.push({cx, cy});
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j)
            ans = max(ans, distance[i][j]);
    cout << ans << endl;
}

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

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

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

Output: 3