इस ट्यूटोरियल में, हम 0s की गिनती खोजने के लिए एक प्रोग्राम पर चर्चा करेंगे जो एक बाइनरी मैट्रिक्स में 1s द्वारा ब्लॉक किया गया है।
इसके लिए हमें एक बाइनरी मैट्रिक्स प्रदान किया जाएगा। हमारा काम मैट्रिक्स में उन सभी 0 को ढूंढना और गिनना है जो 1s द्वारा अवरुद्ध हैं।
उदाहरण
#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