leetcode:102. 沉没孤岛
题目
题目描述：
给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。
现在你需要将所有孤岛“沉没”，即将孤岛中的所有陆地单元格（1）转变为水域单元格（0）。
输入描述：
第一行包含两个整数 N, M，表示矩阵的行数和列数。
之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。
输出描述
输出将孤岛“沉没”之后的岛屿矩阵。
输入示例：
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
输出示例：
1 1 0 0 0
1 1 0 0 0
0 0 0 0 0
0 0 0 1 1思路
这道题跟求孤岛面积很像，我们还是从边缘的岛屿来考虑，把边缘的岛屿全部做上标记（不是0和1，这里用2来表示它是靠边的，不是中间的），然后遍历整个网格，如果遇到了1，说明就是中间的孤岛，把它变成0.
最后一步：把之前标记为2的，全部返回标记成1！
#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
// 将周围岛屿标记（注意是标记为2）
void dfs(vector<vector<int>> &grid, int x, int y)
{
// 终止条件（这里可能是遇到海水，还可能是遇到我们之前标记过的2！！！）
if (grid[x][y] == 0 || grid[x][y] == 2)
return;
// 处理当前节点
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;
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])
dfs(grid, n - 1, j);
}
// 现在孤岛是1，把它变成0
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (grid[i][j] == 1)
grid[i][j] = 0;
}
}
// 把非孤岛2全部还原成1
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
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;
}总结
dfs终止条件那部分，注意需要加上遇到2的情况，不然就会把所有2又全部算进去了。