ในปัญหานี้ เราได้รับเมทริกซ์ไบนารี 2 มิติ ภารกิจของเราคือ หาจำนวนเกาะโดยใช้ DFS
เกาะ (Island) คือกลุ่มของ 1 หรือมากกว่าที่เชื่อมต่อกันในเมทริกซ์
มาดูตัวอย่างเพื่อเข้าใจปัญหา
Input : bin[][] = {{ 1 0 0 0} {0 1 0 1} {0 0 0 0} {0 0 1 0}} Output : 3 คำอธิบาย
เกาะคือ −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
