題1：

指路：101. 孤島的總面積 (kamacoder.com)

思路與代碼：

本題要求找到不靠邊的陸地面積，那么我們從地圖的最外層開始遍歷，找到靠近四個邊的陸地，通過搜索將周邊靠陸地且相鄰的陸地1變成海洋0，重新遍歷地圖統計剩下的陸地1即可。代碼如下：

#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;
}

題2：

指路：102. 沉沒孤島 (kamacoder.com)

思路與代碼：

本題與上題的區別在于，要將孤島1變成水域0，從地圖周邊開始，在空格相鄰的陸地標記，遍歷地圖遇到陸地且無標記的變成水域1即可。其中，無需另外定義一個二維數組將陸地與原數組對比比較，可以直接將陸地實行特殊標記2。首先，dfs將地圖周邊的陸地1變成特殊標記2，然后將水域0中間的陸地1變成水域0，最后將特殊標記2改成陸地1即可。代碼如下：

#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;}// return 0;
}

題3：

指路：103. 水流問題 (kamacoder.com)

思路與代碼：

要求節點能到達第以一邊界和第二邊界。遍歷即可，如果這個節點能同時到達第一和第二邊界，那么該節點符合結果集條件，寫出來發現超時(見下面代碼中的灰色注釋部分)。那么對其進行優化：從第一組邊界和第二組邊界開始遍歷，標記遍歷過的節點，如果同時標記則表示節點可到達。代碼如下：

#include<iostream>
#include<vector>
using namespace std;
//到達第一邊界或達到第二邊界
//
int n, m;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};// 輔助數組visited
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;if (grid[x][y] > grid[nextx][nexty]) continue;dfs (grid, visited, nextx, nexty);}return ;
}/*  bool isResult (vector<vector<int>>& grid, int x, int y) {vector<vector<bool>> visited(n, vector<bool> (m, false)) ;dfs (grid, visited, x, y);bool isFirst = false;bool isSecond = false;//  第一邊界中的上邊界for (int j = 0; j < m; j++) {if (visited[0][j]) {isFirst = true;break;}}// 第一邊界中的左邊界for (int i = 0; i < n; i++) {if (visited[i][0]) {isFirst = true;break;}}// 第二邊界中的右邊界for (int j = 0;j < m; j++) {if (visited[n - 1][j]) {isSecond = true;break;}}// 第二邊界中的下邊界for (int i = 0; i < n; i++) {if (visited[i][m - 1]) {isSecond = true;break;}}if (isFirst && isSecond) return true;return false;}*/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];}}/* for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (isResult (grid, i, j)) {cout << i << " " << j << endl;}}}*/// 第一組的邊界上的節點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;}}}