ในปัญหานี้ เราได้รับเมทริกซ์ไบนารี 2 มิติ งานของเราคือการหาจำนวนเกาะโดยใช้ DFS
เกาะ เป็นกราวด์ของ 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
