นับ 0 ทั้งหมดที่ถูกบล็อกโดย 1 ในเมทริกซ์ไบนารีใน C++

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมที่หาจำนวน 0 ที่ถูกบล็อกโดย 1 ในเมทริกซ์ไบนารี

สำหรับสิ่งนี้ เราจะได้รับเมทริกซ์ไบนารี งานของเราคือหาและนับ 0 ทั้งหมดในเมทริกซ์ที่ถูกบล็อกโดย 1

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

#include <iostream>
using namespace std;

#define Row 4
#define Col 5

int r[4] = { 0, 0, 1, -1 };
int c[4] = { 1, -1, 0, 0 };

bool isSafe(int x, int y, int M[][Col]) {
    if (x >= 0 && x <= Row && y >= 0 &&
        y <= Col && M[x][y] == 0)
        return true;
    return false;
}

//performing DFS in the matrix
void DFS(int x, int y, int M[][Col]) {
    //marking the node as visited
    M[x][y] = 1;
    for (int k = 0; k < 4; k++)
        if (isSafe(x + r[k], y + c[k], M))
            DFS(x + r[k], y + c[k], M);
}

//returning count of blocked 0s
int CountAllZero(int M[][Col]){
    for (int i = 0; i < Col; i++)
        if (M[0][i] == 0)
            DFS(0, i, M);
    for (int i = 0; i < Col; i++)
        if (M[Row - 1][i] == 0)
            DFS(Row - 1, i, M);
    for (int i = 0; i < Row; i++)
        if (M[i][0] == 0)
            DFS(i, 0, M);
    for (int i = 0; i < Row; i++)
        if (M[i][Col - 1] == 0)
            DFS(i, Col - 1, M);
    //counting all zeros which are surrounded by 1
    int result = 0;
    for (int i = 0; i < Row; i++)
        for (int j = 0; j < Col; j++)
            if (M[i][j] == 0)
                result++;
    return result;
}

int main(){
    int M[][Col] = { { 1, 1, 1, 0, 1 },{ 1, 0, 0, 1, 0 },{ 1, 0, 1, 0, 1 },{ 0, 1, 1, 1, 1 } };
    cout << CountAllZero(M) << endl;
    return 0;
}

ผลลัพธ์

4