এই সমস্যায়, আমাদের একটি 2D বাইনারি ম্যাট্রিক্স দেওয়া হয়েছে। আমাদের কাজ হল DFS ব্যবহার করে দ্বীপের সংখ্যা খুঁজে বের করা।
দ্বীপ ম্যাট্রিক্সে 1 বা তার বেশি সংযুক্ত 1 এর গ্রাউন্ড।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input : bin[][] = {{ 1 0 0 0}
{0 1 0 1}
{0 0 0 0}
{0 0 1 0}}
Output : 3
Explanation
Islands are −bin00 - bin11
bin13
bin32
সমাধান পদ্ধতি
DFS ব্যবহার করে সমস্যা সমাধানের জন্য, আমরা সমস্ত প্রতিবেশী (ম্যাট্রিক্সে একটি সংখ্যার সর্বোচ্চ সম্ভাব্য 8) অন্বেষণ করার জন্য DFS কৌশল ব্যবহার করব এবং 1 এর জন্য পরীক্ষা করব। যদি আমরা 1টি মান দেখতে পাই যা দেখা না হয়, তাহলে আমরা এটি বিবেচনা করব। আমরা বারবার পরিদর্শন এড়াতে পরিদর্শন করা মানগুলির উপর নজর রাখব। এটি করে, আমরা ম্যাট্রিক্সে উপস্থিত দ্বীপের সংখ্যা গণনা করতে পারি।
গ্রাফে ডিএফএস শিখুন
গ্রাফ সম্পর্কে জানুন
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
#define ROW 5
#define COL 5
int canVisit(int bin[][COL], int row, int col, bool visited[][COL]){
return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (bin[row][col] && !visited[row][col]);
}
void DFS(int bin[][COL], int row, int col, bool visited[][COL]){
static int getNeighbourRow[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
static int getNeighbourCol[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
visited[row][col] = true;
for (int k = 0; k < 8; ++k)
if (canVisit(bin, row + getNeighbourRow[k], col + getNeighbourCol[k], visited))
DFS(bin, row + getNeighbourRow[k], col + getNeighbourCol[k], visited);
}
int findIslandCount(int bin[][COL]){
bool visited[ROW][COL];
memset(visited, 0, sizeof(visited));
int islandCount = 0;
for (int i = 0; i < ROW; ++i)
for (int j = 0; j < COL; ++j)
if (bin[i][j] && !visited[i][j]) {
DFS(bin, i, j, visited);
islandCount++;
}
return islandCount;
}
int main(){
int bin[][COL] = {{1, 0, 0, 0},
{0, 1, 0, 1},
{0, 0, 0, 0},
{0, 0, 1, 0}};
cout<<"The number of islands present in the matrix is "<<findIslandCount(bin);
return 0;
} আউটপুট
The number of islands present in the matrix is 4
