এই টিউটোরিয়ালে, আমরা একটি বাইনারি ম্যাট্রিক্সে 1s দ্বারা ব্লক করা 0s গণনা খুঁজে বের করার জন্য একটি প্রোগ্রাম নিয়ে আলোচনা করব।
এর জন্য আমাদের একটি বাইনারি ম্যাট্রিক্স প্রদান করা হবে। আমাদের কাজ হল ম্যাট্রিক্সে 1s দ্বারা ব্লক করা সমস্ত 0s খুঁজে বের করা এবং গণনা করা।
উদাহরণ
#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
