Number of Enclaves ใน C++

คำอธิบายปัญหา

กำหนดกริด 2D ที่แต่ละเซลล์เป็น 0 (น้ำ) หรือ 1 (บก) สามารถเดินจากบกไปบกได้ 4 ทิศทาง (บน ล่าง ซ้าย ขวา) ต้องการนับจำนวนเซลล์บกที่ ไม่สามารถเดินออกนอกขอบกริดได้ (enclaves)

ตัวอย่าง: กริด 4x4 มี enclaves 3 เซลล์

วิธีแก้ปัญหา (DFS/BFS จากขอบ)

1. ทำ DFS/BFS จากเซลล์บกที่อยู่บนขอบกริด (แถวแรก/สุดท้าย, คอลัมน์แรก/สุดท้าย)
2. ทำเครื่องหมายเซลล์ที่ไปถึงได้จากขอบเป็น "ปลอดภัย" (เช่น เปลี่ยนเป็น 0)
3. หลังจากนั้น นับเซลล์บกที่เหลือ (ซึ่งคือ enclaves)

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

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

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

class Solution {
public:
    void dfs(int x, int y, vector<vector<int>>& A) {
        if(x < 0 || y < 0 || x >= A.size() || y >= A[0].size() || A[x][y] == 0)
            return;
        A[x][y] = 0;
        for(int k = 0; k < 4; k++) {
            int nx = x + dir[k][0];
            int ny = y + dir[k][1];
            dfs(nx, ny, A);
        }
    }
    
    int numEnclaves(vector<vector<int>>& A) {
        int n = A.size();
        int m = n ? A[0].size() : 0;
        
        // กำจัดบกที่เชื่อมต่อขอบ
        for(int i = 0; i < n; i++) {
            if(A[i][0] == 1) dfs(i, 0, A);
            if(A[i][m-1] == 1) dfs(i, m-1, A);
        }
        for(int j = 0; j < m; j++) {
            if(A[0][j] == 1) dfs(0, j, A);
            if(A[n-1][j] == 1) dfs(n-1, j, A);
        }
        
        // นับ enclaves ที่เหลือ
        int ret = 0;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                ret += A[i][j];
        return ret;
    }
};

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

อินพุต

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

เอาต์พุต

3