Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm số lượng các số 0 bị chặn bởi các số 1 trong một ma trận nhị phân.
Đối với điều này, chúng tôi sẽ được cung cấp một ma trận nhị phân. Nhiệm vụ của chúng ta là tìm và đếm tất cả các số 0 trong ma trận bị chặn bởi các số 1.
Ví dụ
#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;
} Đầu ra
4