題目描述：

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

輸入描述：

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

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

輸出描述：

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

版本一調用dfs 的條件判斷，放在，版本二的終止條件位置上。（dfs函數內部有差別）

版本一的寫法：下一個節點是否能合法已經判斷完了，傳進dfs函數的就是合法節點。

版本二的寫法：不管節點是否合法，上來就dfs，然后在終止條件的地方進行判斷，不合法再return。

理論上來講，版本一的效率更高一些，因為避免了沒有意義的遞歸調用，在調用dfs之前，就做合法性判斷。但從寫法來說，可能版本二更利于理解一些。

版本一：

• dfs函數直接處理傳入節點連接的四個節點
• 所以主函數中需要先將這個傳入節點的visited數組值設為true，再dfs處理連接的節點
• dfs函數中，連接的節點被判斷為未訪問的島嶼后，再對其visited數組值設為true，再dfs處理連接的節點

兩個區別：visited再哪里設置；未訪問島嶼在哪里判斷

#include <iostream>
#include <vector>
using namespace std;int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 四個方向
void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {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; // 越界了，跳過，換個方向搜索if (visited[nextx][nexty] == false && grid[nextx][nexty] == 1) { // 未訪問過，同時，是陸地（grid = 1）才繼續搜索，不是陸地就直接搜索下一個方向（只能橫豎連著才算一個島）visited[nextx][nexty] = true;dfs(grid, visited, nextx, nexty);}}
}int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}vector<vector<bool>> visited(n, vector<bool>(m, false)); // 訪問數組，記錄有沒有訪問過int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (visited[i][j] == false && grid[i][j] == 1) {visited[i][j] = true;result++; // 遇到沒訪問過的陸地，+1dfs(grid, visited, i, j); // 將與這個沒訪問陸地連接的陸地都標記上true，他們屬于同一個島，防止這些點繼續被訪問，被錯誤的計算為“未發現的新島”，影響result計數；（！！保證連在一起的一個島只被計數一次！！）}}}cout << result << endl;
}

版本二：?

• dfs函數直接處理傳入節點
• 所以主函數中，可以直接用dfs處理該節點
• dfs函數中，先判斷該節點是不是未訪問的島嶼；不是就return，是就對其visited數組值設為true，再dfs處理連接的節點

兩個區別：visited再哪里設置；未訪問島嶼在哪里判斷

#include <iostream>
#include <vector>
using namespace std;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 四個方向
void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {if (visited[x][y] == true || grid[x][y] == 0) return; // 終止條件：訪問過的節點 或者 遇到海水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(grid, visited, nextx, nexty);}
}int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}vector<vector<bool>> visited(n, vector<bool>(m, false));int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (visited[i][j] == false && grid[i][j] == 1) {result++; // 遇到沒訪問過的陸地，+1dfs(grid, visited, i, j); // 將與其鏈接的陸地都標記上 true}}}cout << result << endl;
}

重點：加入隊列就代表走過，立即標記，而不是從隊列拿出來的時候再去標記。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 四個方向
void bfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) { // 先加入本點，標記本點，再處理連接的四個點queue<pair<int, int>> que;que.push({x, y});visited[x][y] = true; // 只要加入隊列，立即標記while(!que.empty()) {pair<int, int> cur = que.front();que.pop(); // 隊列前面元素出隊列，處理它連接的四個點for (int i = 0; i < 4; i++) {int nextx = cur.first + dir[i][0];int nexty = cur.second + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界了，直接跳過，搜索當前點的下一個方向if (visited[nextx][nexty] == false && grid[nextx][nexty] == 1) {que.push({nextx, nexty});visited[nextx][nexty] = true; // 只要加入隊列，立即標記}}}
}
int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}vector<vector<bool>> visited(n, vector<bool>(m, false));int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (visited[i][j] == false && grid[i][j] == 1) {result++; // 遇到沒訪問過的陸地，+1bfs(grid, visited, i, j); // 直接處理這個點，并將與其鏈接的陸地都標記上 true}}}cout << result << endl;
}

3.100島嶼的最大面積100. 島嶼的最大面積

題目描述

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

輸入描述

第一行包含兩個整數 N, M，表示矩陣的行數和列數。后續 N 行，每行包含 M 個數字，數字為 1 或者 0，表示島嶼的單元格。

輸出描述

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

版本一dfs：dfs處理當前節點的相鄰節點，即主函數遇到島嶼就計數為1，dfs處理接下來的相鄰陸地?

#include <iostream>
#include <vector>
using namespace std;
int count;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 四個方向
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {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;  // 越界了，直接跳過if (visited[nextx][nexty] == false && grid[nextx][nexty] == 1) { // 在這里判斷；沒有訪問過的,同時是陸地的visited[nextx][nexty] = true; // 在這里處理count++; // 在這里處理；累計傳入節點的連接節點的面積dfs(grid, visited, nextx, nexty);}}
}int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}vector<vector<bool>> visited(n, vector<bool>(m, false));int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (visited[i][j] == false && grid[i][j] == 1) {visited[i][j] = true; // 下面的dfs是處理相連節點的，所以這里要把當前節點visited數組值設置完count = 1;  // 因為下面的dfs處理下一個與之相連的節點，所以這里遇到陸地了就先計數，dfs處理接下來的相鄰陸地dfs(grid, visited, i, j); // 將與其鏈接的陸地都標記上 trueresult = max(result, count);}}}cout << result << endl;}

版本二dfs：dfs處理當前節點，即主函數遇到島嶼就計數為0，dfs處理接下來的全部陸地

#include <iostream>
#include <vector>
using namespace std;
int count;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 四個方向
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {if (visited[x][y] == true || grid[x][y] == 0) return; // 在這里判斷；終止條件：訪問過的節點 或者 遇到海水visited[x][y] = true; // 在這里處理；因為main里的dfs處理當前節點，所以main中不需要處理當前節點的visited數組值，放在這里處理count++; // 在這里處理；因為main里的dfs處理當前節點，所以main中不需要考慮當前節點的面積，放在這里處理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(grid, visited, nextx, nexty);}
}int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false));int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (visited[i][j] == false && grid[i][j] == 1) {count = 0; // 因為dfs處理當前節點，所以遇到陸地計數為0，（現在還不需要考慮它的面積，因為交給后序dfs考慮了）進dfs之后在開始從1計數dfs(grid, visited, i, j); // 將與其鏈接的陸地都標記上 trueresult = max(result, count);}}}cout << result << endl;
}

版本三bfs寫法：處理當前節點，所以count++放在bfs函數里面的前面

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int count;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 四個方向
void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {queue<pair<int, int>> que;que.push({x, y});visited[x][y] = true; // 加入隊列就意味節點是陸地可到達的點count++;while(!que.empty()) {pair<int, int> cur = que.front();que.pop();for (int i = 0 ;i < 4; i++) {int nextx = cur.first + dir[i][0];int nexty = cur.second + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界if (visited[nextx][nexty] == false && grid[nextx][nexty] == 1) { // 節點沒有被訪問過且是陸地visited[nextx][nexty] = true;count++;que.push({nextx, nexty});}}}
}int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}vector<vector<bool>> visited(n, vector<bool>(m, false));int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (visited[i][j] == false && grid[i][j] == 1) {count = 0;bfs(grid, visited, i, j); // 將與其鏈接的陸地都標記上 trueresult = max(result, count);}}}cout << result << endl;
}

4.101孤島的總面積101. 孤島的總面積

題目描述

給定一個由 1（陸地）和 0（水）組成的矩陣，島嶼指的是由水平或垂直方向上相鄰的陸地單元格組成的區域，且完全被水域單元格包圍。孤島是那些位于矩陣內部、所有單元格都不接觸邊緣的島嶼。

現在你需要計算所有孤島的總面積，島嶼面積的計算方式為組成島嶼的陸地的總數。

輸入描述

第一行包含兩個整數 N, M，表示矩陣的行數和列數。之后 N 行，每行包含 M 個數字，數字為 1 或者 0。

輸出描述

輸出一個整數，表示所有孤島的總面積，如果不存在孤島，則輸出 0。

版本一dfs：dfs處理當前節點的連接節點?

#include <iostream>
#include <vector>
using namespace std;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 四個方向
void dfs(vector<vector<int>>& grid, int x, int y) {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; // 超過邊界，不符合條件，不繼續遍歷if (grid[nextx][nexty] == 1) {grid[nextx][nexty] = 0;dfs (grid, nextx, nexty);}}
}int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}// 從左側邊，和右側邊 向中間遍歷for (int i = 0; i < n; i++) {if (grid[i][0] == 1) {grid[i][0] = 0;dfs(grid, i, 0);}if (grid[i][m - 1] == 1) {grid[i][m - 1] = 0;dfs(grid, i, m - 1);}}// 從上邊和下邊 向中間遍歷for (int j = 0; j < m; j++) {if (grid[0][j] == 1) {grid[0][j] = 0;dfs(grid, 0, j);}if (grid[n - 1][j] == 1) {grid[n - 1][j] = 0;dfs(grid, n - 1, j);}}int count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) count++;}}cout << count << endl;
}

版本二dfs：dfs直接處理當前節點

#include <iostream>
#include <vector>
using namespace std;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 四個方向
void dfs(vector<vector<int>>& grid, int x, int y) {if (grid[x][y] == 0) return;grid[x][y] = 0;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 (grid, nextx, nexty);}
}int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}// 從左側邊，和右側邊 向中間遍歷for (int i = 0; i < n; i++) {if (grid[i][0] == 1) dfs(grid, i, 0);if (grid[i][m - 1] == 1) dfs(grid, i, m - 1);}// 從上邊和下邊 向中間遍歷for (int j = 0; j < m; j++) {if (grid[0][j] == 1) dfs(grid, 0, j);if (grid[n - 1][j] == 1) dfs(grid, n - 1, j);}int count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) count++;}}cout << count << endl;
}

bfs：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 四個方向
void bfs(vector<vector<int>>& grid, int x, int y) {queue<pair<int, int>> que;que.push({x, y});grid[x][y] = 0; // 只要加入隊列，立刻標記while(!que.empty()) {pair<int ,int> cur = que.front(); que.pop();for (int i = 0; i < 4; i++) {int nextx = cur.first + dir[i][0];int nexty = cur.second + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳過if (grid[nextx][nexty] == 1) {que.push({nextx, nexty});grid[nextx][nexty] = 0; // 只要加入隊列立刻標記}}}
}int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}// 從左側邊，和右側邊 向中間遍歷for (int i = 0; i < n; i++) {if (grid[i][0] == 1) bfs(grid, i, 0);if (grid[i][m - 1] == 1) bfs(grid, i, m - 1);}// 從上邊和下邊 向中間遍歷for (int j = 0; j < m; j++) {if (grid[0][j] == 1) bfs(grid, 0, j);if (grid[n - 1][j] == 1) bfs(grid, n - 1, j);}int count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) count++;}}cout << count << endl;
}