卡码网KamaCoder 102. 沉没孤岛

题目来源：102. 沉没孤岛

C++题解：深度优先搜索。

先找到不是孤岛的岛屿并标注visited为true，之后把岛屿（grid为1）并且不是岸边（visited为false）的孤岛沉没（输出0）。

#include <iostream>
#include <vector>using namespace std;void dfs(vector<vector<int>> &grid, vector<vector<bool>> &visited, int i, int j){if(visited[i][j] || grid[i][j] == 0) return;visited[i][j] = true;if(i+1 < grid.size()) dfs(grid, visited, i+1, j);if(j+1 < grid[0].size()) dfs(grid, visited, i, j+1);if(i-1 > 0) dfs(grid, visited, i-1, j);if(j-1 > 0) dfs(grid, visited, i, j-1);return;
}int main(){int N, M;cin>>N>>M;vector<vector<int>> grid(N+1, vector<int>(M+1, 0));vector<vector<bool>> visited(N+1, vector<bool>(M+1, false));// 输入for(int i = 1; i <= N; i++) {for(int j = 1; j <= M; j++){cin>>grid[i][j];}}// 寻找靠岸的岛并标记for(int i = 1; i <= N; i++){dfs(grid, visited, i, 1);dfs(grid, visited, i, M);}    for(int j = 1; j <= M; j++){dfs(grid, visited, 1, j);dfs(grid, visited, N, j);}// 输出for(int i = 1; i <= N; i++) {for(int j = 1; j <= M; j++){if(grid[i][j] == 1 && visited[i][j]) cout<<1;else cout<<0;if(j != M) cout<<" ";}if(i != N) cout<<endl;}return 0;
}