目錄

101.孤島的總面積

圖論法

102.沉沒孤島

圖論法

103.水流問題

圖論法

104.建造最大島嶼

圖論法

---

101.孤島的總面積

• 題目鏈接：101. 孤島的總面積

• 文章講解：代碼隨想錄

圖論法

• 代碼一：深搜

#include <iostream>
#include <vector>
using namespace std;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四個方向
int count; // 統計符合題目要求的陸地空格數量
void dfs(vector<vector<int>>& grid, int x, int y) {grid[x][y] = 0;count++;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] == 0) continue;dfs (grid, nextx, nexty);}return;
}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);}count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) dfs(grid, i, j);}}cout << count << endl;
}

• 代碼二：廣搜

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int count = 0;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四個方向
void bfs(vector<vector<int>>& grid, int x, int y) {queue<pair<int, int>> que;que.push({x, y});grid[x][y] = 0; // 只要加入隊列，立刻標記count++;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 (grid[nextx][nexty] == 1) {que.push({nextx, nexty});count++;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);}count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) bfs(grid, i, j);}}cout << count << endl;
}

102.沉沒孤島

• 題目鏈接：102. 沉沒孤島

• 文章講解：代碼隨想錄

圖論法

• 代碼一：dfs

#include <iostream>
#include <vector>
using namespace std;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四個方向
void dfs(vector<vector<int>>& grid, int x, int y) {grid[x][y] = 2;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] == 0 || grid[nextx][nexty] == 2) continue;dfs (grid, nextx, nexty);}return;
}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);}// 步驟二、步驟三for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) grid[i][j] = 0;if (grid[i][j] == 2) grid[i][j] = 1;}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cout << grid[i][j] << " ";}cout << endl;}
}

103.水流問題

• 題目鏈接：103. 水流問題

• 文章講解：代碼隨想錄

圖論法

• 代碼一：dfs

#include <iostream>
#include <vector>
using namespace std;
int n, m;
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 (visited[x][y]) 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 >= n || nexty < 0 || nexty >= m) continue;if (grid[x][y] > grid[nextx][nexty]) continue; // 注意：這里是從低向高遍歷dfs (grid, visited, nextx, nexty);}return;
}int main() {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>> firstBorder(n, vector<bool>(m, false));// 標記從第一組邊界上的節點出發，可以遍歷的節點vector<vector<bool>> secondBorder(n, vector<bool>(m, false));// 從最上和最下行的節點出發，向高處遍歷for (int i = 0; i < n; i++) {dfs (grid, firstBorder, i, 0); // 遍歷最左列，接觸第一組邊界dfs (grid, secondBorder, i, m - 1); // 遍歷最右列，接觸第二組邊界}// 從最左和最右列的節點出發，向高處遍歷for (int j = 0; j < m; j++) {dfs (grid, firstBorder, 0, j); // 遍歷最上行，接觸第一組邊界dfs (grid, secondBorder, n - 1, j); // 遍歷最下行，接觸第二組邊界}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 如果這個節點，從第一組邊界和第二組邊界出發都遍歷過，就是結果if (firstBorder[i][j] && secondBorder[i][j]) cout << i << " " << j << endl;;}}}

104.建造最大島嶼

• 題目鏈接：104. 建造最大島嶼

• 文章講解：代碼隨想錄

圖論法

• 代碼一：深搜

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;
int n, m;
int count;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, int mark) {if (visited[x][y] || grid[x][y] == 0) return; // 終止條件：訪問過的節點 或者 遇到海水visited[x][y] = true; // 標記訪問過grid[x][y] = mark; // 給陸地標記新標簽count++;for (int i = 0; i < 4; i++) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;  // 越界了，直接跳過dfs(grid, visited, nextx, nexty, mark);}
}int main() {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)); // 標記訪問過的點unordered_map<int ,int> gridNum;int mark = 2; // 記錄每個島嶼的編號bool isAllGrid = true; // 標記是否整個地圖都是陸地for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 0) isAllGrid = false;if (!visited[i][j] && grid[i][j] == 1) {count = 0;dfs(grid, visited, i, j, mark); // 將與其鏈接的陸地都標記上 truegridNum[mark] = count; // 記錄每一個島嶼的面積mark++; // 記錄下一個島嶼編號}}}if (isAllGrid) {cout << n * m << endl; // 如果都是陸地，返回全面積return 0; // 結束程序}// 以下邏輯是根據添加陸地的位置，計算周邊島嶼面積之和int result = 0; // 記錄最后結果unordered_set<int> visitedGrid; // 標記訪問過的島嶼for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {count = 1; // 記錄連接之后的島嶼數量visitedGrid.clear(); // 每次使用時，清空if (grid[i][j] == 0) {for (int k = 0; k < 4; k++) {int neari = i + dir[k][1]; // 計算相鄰坐標int nearj = j + dir[k][0];if (neari < 0 || neari >= n || nearj < 0 || nearj >= m) continue;if (visitedGrid.count(grid[neari][nearj])) continue; // 添加過的島嶼不要重復添加// 把相鄰四面的島嶼數量加起來count += gridNum[grid[neari][nearj]];visitedGrid.insert(grid[neari][nearj]); // 標記該島嶼已經添加過}}result = max(result, count);}}cout << result << endl;}