Ô nước xa đất nhất trong C++

Mô tả bài toán

Cho lưới N x N giá trị 0 (nước) và 1 (đất). Tìm ô nước có khoảng cách Manhattan lớn nhất đến đất gần nhất. Trả về khoảng cách đó, hoặc -1 nếu không có đất hoặc không có nước.

Ví dụ: Lưới 3x3 có đất ở 4 góc → ô giữa (1,1) có khoảng cách 2.

Giải thuật BFS đa nguồn (Multi-source BFS)

1. Đưa tất cả ô đất vào hàng đợi, gán khoảng cách = 0.
2. BFS lan truyền sang 4 hướng (trên/dưới/trái/phải).
3. Mỗi ô nước lần đầu được ghé thăm có khoảng cách = khoảng cách ô cha + 1.
4. Theo dõi khoảng cách lớn nhất gặp được.

Đây là BFS chuẩn từ nhiều nguồn, đảm bảo tìm được khoảng cách ngắn nhất từ mỗi ô nước đến đất gần nhất.

Cài đặt C++

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

class Solution {
    int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
public:
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size();
        queue<pair<int,int>> q;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 1) q.emplace(i, j);
        if (q.empty() || q.size() == n*n) return -1; // toàn đất hoặc toàn nước
        
        int dist = -1;
        while (!q.empty()) {
            int sz = q.size();
            while (sz--) {
                auto [x, y] = q.front(); q.pop();
                for (auto& d : dirs) {
                    int nx = x + d[0], ny = y + d[1];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= n || grid[nx][ny]) continue;
                    grid[nx][ny] = 1; // đánh dấu đã thăm
                    q.emplace(nx, ny);
                }
            }
            dist++;
        }
        return dist;
    }
};

int main() {
    vector<vector<int>> v = {{1,0,1},{0,0,0},{1,0,1}};
    Solution ob;
    cout << ob.maxDistance(v); // 2
    return 0;
}

Độ phức tạp

• Thời gian: O(N^2).
• Không gian: O(N^2) cho hàng đợi.