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

ソリューションアプローチ

DFSを使用して問題を解決するために、DFS手法を使用して、すべてのネイバー（マトリックス内の数値の最大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