1.島嶼數量（深搜）?---》模板題

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

#include <iostream>
#include <vector>
using namespace std;int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四個方向
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] &&grid[nextx][nexty] == 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] && grid[i][j] == 1) {visited[i][j] = true;result++;                 // 遇到沒訪問過的陸地，+1dfs(grid, visited, i, j); // 將與其鏈接的陸地都標記上 true}}}cout << result << endl;
}

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

void dfs(const vector<vector<int>> &grid, vector<vector<bool>> &visited, int x, int y)
{if(visited[x][y]||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()
{...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] && grid[i][j] == 1){result++;                 // 遇到沒訪問過的陸地，+1dfs(grid, visited, i, j); // 將與其鏈接的陸地都標記上 true}}}cout << result << endl;
}

但是版本一比版本二要高效，避免了無用的遞歸。

2.島嶼數量（廣搜）

只要 加入隊列就代表 走過，就需要標記，而不是從隊列拿出來的時候再去標記走過.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四個方向
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();int curx = cur.first;int cury = cur.second;for(int i = 0; i < 4; i++){int nextx = curx + dir[i][0];int nexty = cury + dir[i][1];if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;if(!visited[nextx][nexty]&&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] && grid[i][j] == 1){result++;                 // 遇到沒訪問過的陸地，+1bfs(grid, visited, i, j); // 將與其鏈接的陸地都標記上 true}}}cout << result << endl;
}

3.島嶼的最大面積

#include <iostream>
#include <vector>
using namespace std;int count = 0;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
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 || nexty < 0 || nextx >= grid.size() ||nexty >= grid[0].size()) {continue;}if(!visited[nextx][nexty]&&grid[nextx][nexty]==1){visited[nextx][nexty] = true;count++;dfs(grid,visited,nextx,nexty);}}
}int main(void) {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] && grid[i][j] == 1) {visited[i][j] = true;count=1;//重置dfs(grid, visited, i, j);result = max(result, count);}}}cout<<result<<endl;return 0;
}