এই সমস্যাতে, আমাদের একটি ২D বাইনারি ম্যাট্রিক্স দেওয়া আছে। আমাদের কাজ হল DFS ব্যবহার করে দ্বীপের সংখ্যা বের করা।
দ্বীপ (Island) হল ম্যাট্রিক্সে ১ বা অধিক সংযুক্ত ১-এর গোষ্ঠী।
উদাহরণ দেখি:
ইনপুট : bin[][] = {{ 1 0 0 0} {0 1 0 1} {0 0 0 0} {0 0 1 0}} আউটপুট : 3 ব্যাখ্যা
দ্বীপগুলো −bin00 - bin11
bin13
bin32
সমাধানের পদ্ধতি
DFS ব্যবহার করে সমাধান করতে, আমরা একটি নম্বারের সব প্রতিবেশী (ম্যাক্সিমাম ৮টি) এক্সপ্লোর করব এবং ১ খুঁজে বের করব। যদি অনভিজিটেড ১ পাওয়া যায়, তবে সেটি ধরে রাখব। ভিজিটেড মানগুলো ট্র্যাক রাখব যাতে পুনরাবৃত্তি না হয়। এভাবে ম্যাট্রিক্সে কয়টি দ্বীপ আছে সেটি কাউন্ট করা যায়।
উদাহরণ
#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
