এই টিউটোরিয়ালে, একটি বাইনারি ম্যাট্রিক্স দেওয়া থাকে। ম্যাট্রিক্সের বর্ডার থেকে DFS করে বাইরের ০গুলো চিহ্নিত করুন। বাকি অবিচিহ্নিত ০গুলোই ১ দ্বারা ব্লক করা ০।
C++ প্রোগ্রাম উদাহরণ
#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;
}
void DFS(int x, int y, int M[][Col]) {
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);
}
int CountAllZero(int M[][Col]) {
// বর্ডার থেকে DFS
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);
// অবিচিহ্নিত ০ গণনা
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
