leetcode:99. 島嶼數量

題目

題目描述：

給定一個由 1（陸地）和 0（水）組成的矩陣，你需要計算島嶼的數量。島嶼由水平方向或垂直方向上相鄰的陸地連接而成，并且四周都是水域。你可以假設矩陣外均被水包圍。

輸入描述：

第一行包含兩個整數 N, M，表示矩陣的行數和列數。

后續 N 行，每行包含 M 個數字，數字為 1 或者 0。

輸出描述：

輸出一個整數，表示島嶼的數量。如果不存在島嶼，則輸出 0。

思路

遇到一個沒有遍歷過的節點陸地，計數器就加一，然后把該節點陸地所能遍歷到的陸地都標記上（這一步就是為了防止重復計算!）。

在遇到標記過的陸地節點和海洋節點的時候直接跳過.

計數器就是最終島嶼的數量。

下面代碼詳細注釋：

#include <bits/stdc++.h>
using namespace std;// 定義4個方向
int dir[4][2] = {1, 0, 0, -1, -1, 0, 0, 1};void dfs(vector<vector<int>> &grid, vector<vector<bool>> &visited, int x, int y)
{// 終止條件：如果遇到海水或者已經遍歷過的島嶼就停下來if (grid[x][y] == 0 || visited[x][y]){return;}// 處理當前節點：當前到了(x,y)這個點，首先就把它標記上visited[x][y] = true;// 當前節點往下延伸，看它四周的點for (int i = 0; i < 4; i++){int nextx = x + dir[i][0];int nexty = y + dir[i][1];// 基本限制條件：下一個點肯定不能跑到整個大矩陣的外面去if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size())continue;// 遞歸：這里遞歸不需要任何條件，因為一進入dfs就會有終止條件來判斷dfs(grid, visited, nextx, nexty);}
}int main()
{int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));vector<vector<bool>> visited(n, vector<bool>(m, false));for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){cin >> grid[i][j];}}// count最終島嶼計數int count = 0;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){// 一個一個陸地開始找，不要覺得麻煩，因為有的陸地已經被標記了，就會直接跳過if (grid[i][j] == 1 && !visited[i][j]){count++;dfs(grid, visited, i, j);}}}cout << count << endl;return 0;
}

一定要清楚dfs在這里的作用：

對（x,y）周圍的島嶼進行標記！?

總結

我這里寫的是dfs的第二個模板，第一個模版因為沒有終止條件，所以寫起來感覺很奇怪，我就沒有放，感興趣去看隨想錄。

參考資料

代碼隨想錄?