Khoảng cách gần nhất đến ô giá trị 1 trong ma trận nhị phân C++

Cho ma trận nhị phân (0/1). Với mỗi ô, tìm khoảng cách Manhattan đến ô 1 gần nhất.

Ví dụ

Input:

0 0 1
1 1 0
0 0 0

1 1 0
0 0 1
1 1 2

Thuật toán BFS đa nguồn (Multi-source BFS) - O(N×M)

• Đưa tất cả ô giá trị 1 vào hàng đợi, distance = 0.
• BFS lan truyền: ô láng giềng chưa gán distance → distance = current + 1.

Triển khai C++ (BFS tối ưu)

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

vector> nearestOne(vector>& mat) {
    int R = mat.size(), C = mat[0].size();
    vector> dist(R, vector(C, -1));
    queue> q;

    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            if (mat[i][j] == 1) {
                dist[i][j] = 0;
                q.emplace(i, j);
            }

    int dr[4] = {-1,1,0,0}, dc[4] = {0,0,-1,1};
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr >= 0 && nr < R && nc >= 0 && nc < C && dist[nr][nc] == -1) {
                dist[nr][nc] = dist[r][c] + 1;
                q.emplace(nr, nc);
            }
        }
    }
    return dist;
}

int main() {
    vector> mat = {{0,0,1},{1,1,0},{0,0,0}};
    auto res = nearestOne(mat);
    for (auto& row : res) {
        for (int x : row) cout << x << ' ';
        cout << endl;
    }
    return 0;
}

Kết quả

1 1 0
0 0 1
1 1 2

Lưu ý: Code gốc dùng O(N²M²) (lồng 4 vòng lặp) rất chậm. BFS giảm xuống O(NM).