C++ में DFS का उपयोग करते हुए द्वीपों की संख्या ज्ञात कीजिए

इस समस्या में, हमें एक 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

समाधान दृष्टिकोण

डीएफएस का उपयोग करके समस्या को हल करने के लिए, हम सभी पड़ोसियों (मैट्रिक्स में एक संख्या के अधिकतम संभव 8) की खोज के लिए डीएफएस तकनीक का उपयोग करेंगे और 1 की जांच करेंगे। यदि हम 1 मान का सामना करते हैं जो कि अनदेखा है, तो हम इस पर विचार करेंगे। बार-बार आने से बचने के लिए हम विज़िट किए गए मानों पर नज़र रखेंगे। ऐसा करने से, हम मैट्रिक्स में मौजूद द्वीपों की संख्या गिन सकते हैं।

ग्राफ़ पर 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