Chương trình C++ đếm số vòng lặp để chuyển toàn bộ ô trắng thành đen

Mô tả bài toán

Cho lưới h×w gồm ô đen ('#') và ô trắng ('.'). Mỗi vòng lặp, mọi ô trắng chung cạnh với ô đen sẽ chuyển thành đen. Tìm số vòng lặp cần thiết để toàn bộ lưới thành đen (lưới ban đầu có ít nhất 1 ô đen).

Ví dụ

h=4, w=4, lưới = {"#...", ".#..", "....", "...#"}. Đầu ra: 3.

Thuật toán (BFS đa nguồn)

1. Khởi tạo mảng distance = -1, hàng đợi q.
2. Đưa tất cả ô đen ban đầu vào q với distance = 0.
3. BFS: lấy ô từ q, xét 4 hướng. Nếu ô kề chưa thăm (distance == -1), gán distance = distance[current] + 1 và đẩy vào q.
4. Kết quả là giá trị lớn nhất trong mảng distance.

Đoạn mã 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>> dist(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]=='#') { dist[i][j]=0; q.push({i,j}); }
    while(!q.empty()) {
        auto [x,y] = q.front(); q.pop();
        for(int d=0;d<4;d++) {
            int nx=x+dx[d], ny=y+dy[d];
            if(nx<0||nx>=h||ny<0||ny>=w) continue;
            if(dist[nx][ny]==-1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx,ny});
            }
        }
    }
    int ans = 0;
    for(auto &row: dist) for(int v: row) ans = max(ans, v);
    cout << ans << endl;
}

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

Đầu vào / Đầu ra

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

Output: 3