卡码网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;
}