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