Tìm số hòn đảo bằng cách sử dụng DFS trong C ++

Trong bài toán này, chúng ta được đưa ra một ma trận nhị phân 2D. Nhiệm vụ của chúng ta là Tìm số lượng các hòn đảo bằng DFS.

Đảo là mặt bằng của 1 hoặc nhiều số 1 được kết nối trong ma trận.

Hãy lấy một ví dụ để hiểu vấn đề,

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

Phương pháp tiếp cận giải pháp

Để giải quyết vấn đề bằng cách sử dụng DFS, chúng tôi sẽ sử dụng kỹ thuật DFS để khám phá tất cả các lân cận (tối đa có thể là 8 của một số trong ma trận) và kiểm tra 1’s. Nếu chúng ta gặp 1 giá trị không được hiển thị, thì chúng ta sẽ xem xét nó. Chúng tôi sẽ kiểm tra các giá trị được truy cập để tránh các lần truy cập lặp lại. Làm như vậy, chúng ta có thể đếm số lượng đảo có trong ma trận.

Tìm hiểu DFS trên đồ thị

Tìm hiểu về đồ thị

Ví dụ

#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;
}

Đầu ra

The number of islands present in the matrix is 4