01 Matrix – หาระยะห่าง 0 ใกล้ที่สุดใน C++

ปัญหา: 01 Matrix

กำหนดเมทริกซ์ที่ประกอบด้วย 0 และ 1 หาระยะห่างจากแต่ละเซลล์ไปยัง 0 ใกล้ที่สุด ระยะห่างระหว่างเซลล์ติดกัน = 1 (4 ทิศทาง: บน ลซ ซ้าย ขวา)

ตัวอย่าง

Input:

0 0 0
0 1 0
1 1 1

Output:

0 0 0
0 1 0
1 2 1

แนวทางแก้ปัญหา: Multi-source BFS

เริ่ม BFS จาก ทุกเซลล์ที่เป็น 0 พร้อมกัน (Multi-source) → รับประกันว่าพบระยะห่างสั้นที่สุด

ขั้นตอน

1. สร้างคิว ใส่ ทุกเซลล์ที่เป็น 0 พร้อมตั้งค่าระยะห่าง = 0
2. เซลล์ที่เป็น 1 ตั้งค่าระยะห่าง = INF (ยังไม่รู้)
3. BFS ปกติ: pop เซลล์ → ตรวจสอบ 4 เพื่อนบ้าน → ถ้ายังไม่ได้ไป (ระยะ = INF) → อัปเดตระยะ = ระยะปัจจุบัน + 1 → push เข้าคิว
4. จนคิวว่าง

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

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

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();
        vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
        queue<pair<int,int>> q;

        // Multi-source: ใส่ 0 ทั้งหมดเข้า queue
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (mat[i][j] == 0) {
                    dist[i][j] = 0;
                    q.emplace(i, j);
                }

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

        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            for (auto& d : dir) {
                int nx = x + d[0], ny = y + d[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (dist[nx][ny] != INT_MAX) continue; // visited
                dist[nx][ny] = dist[x][y] + 1;
                q.emplace(nx, ny);
            }
        }
        return dist;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{0,0,0},{0,1,0},{1,1,1}};
    auto res = ob.updateMatrix(v);
    for (auto& row : res) {
        for (int x : row) cout << x << ' ';
        cout << '\n';
    }
    return 0;
}

การทำงานของตัวอย่าง

1. Queue เริ่มต้น: (0,0), (0,1), (0,2), (1,0), (1,2) – ระยะ = 0
2. ขยายไป (1,1) ได้ระยะ 1, (2,0) ระยะ 1, (2,2) ระยะ 1
3. จาก (1,1) ขยายไป (2,1) ได้ระยะ 2

ความซับซ้อน

• เวลา: O(n × m) – แต่ละเซลล์เข้า/ออกคู่อย่างมาก 1 ครั้ง
• พื้นที่: O(n × m) – เก็บระยะห่าง + คิว

ข้อสังเกตสำคัญ

• Multi-source BFS สำคัญ – ถ้า BFS จากแต่ละ 1 แยกกัน จะช้าเป็น O((nm)²)
• ใช้ INT_MAX แทน "ยังไม่ได้ไป" แทน array visited แยกต่างหาก
• โจทย์ LeetCode 542 – เป็นปัญหา BFS คลาสสิก