หาจุดน้ำที่ไกลจากบกที่สุดใน C++

กริด N x N ประกอบด้วย 0 (น้ำ) และ 1 (บก) ต้องการหาช่องน้ำที่มีระยะทางไปยังบกที่ใกล้ที่สุด มากที่สุด (maximin distance) ใช้ระยะทางแมนฮัตตัน |x0-x1| + |y0-y1| หากไม่มีน้ำหรือไม่มีบก ให้คืน -1

ตัวอย่าง:

1 0 1
0 0 0
1 0 1

ขั้นตอนการแก้ปัญหา (Multi-source BFS)

1. เริ่ม BFS จากบกทุกช่องพร้อมกัน (multi-source)
2. เก็บ parent map บอกว่าน้ำแต่ละช่องถูกถึงจากบกช่องไหน
3. ขยาย BFS แบบระดับ (level-order) ทุกครั้งที่ไปช่องน้ำใหม่:
   • คำนวณระยะทางจากบกต้นทาง
   • อัปเดตคำตอบสูงสุด
   • ทำเครื่องหมายช่องนั้นเป็นบก (visited)
4. คืนระยะทางสูงสุดที่พบ

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

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

int dir2[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

class Solution {
public:
    int calcDist(int x1, int y1, int x2, int y2) {
        return abs(x1-x2) + abs(y1-y2);
    }
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size(), m = n ? grid[0].size() : 0;
        map<pair<int,int>, pair<int,int>> parent;
        queue<pair<int,int>> q;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (grid[i][j] == 1) {
                    q.push({i,j});
                    parent[{i,j}] = {i,j};
                }
        int ans = -1;
        while (!q.empty()) {
            int sz = q.size();
            while (sz--) {
                auto [x,y] = q.front(); q.pop();
                for (int k = 0; k < 4; k++) {
                    int nx = x + dir2[k][0], ny = y + dir2[k][1];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= m || grid[nx][ny]) continue;
                    parent[{nx,ny}] = parent[{x,y}];
                    ans = max(ans, calcDist(nx, ny, parent[{x,y}].first, parent[{x,y}].second));
                    q.push({nx,ny});
                    grid[nx][ny] = 1;
                }
            }
        }
        return ans;
    }
};

int main() {
    vector<vector<int>> v1 = {{1,0,1},{0,0,0},{1,0,1}};
    Solution ob;
    cout << ob.maxDistance(v1);
}

Input

[[1,0,1],[0,0,0],[1,0,1]]

Output

2