05沉没孤岛 图论

include

include

using namespace std;
int dir[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
void dfs(int x,int y,vector<vector>& grid,vector<vector>& visited)
{
if(grid[x][y]0 || 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>=grid.size() || nexty<0 || nexty>=grid[0].size()){
continue;
}
dfs(nextx,nexty,grid,visited);
}
}
int main(void)
{
int n,m;
cin >> n >> m;
vector<vector> visited(n,vector(m,false));
vector<vector> grid(n,vector(m,0));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin >> grid[i][j];
}
}
//遍历边界，将边界上的陆地以及与其相连的陆地全部标记，剩余grid中的陆地就是孤岛，将其变成海洋
for(int i=0;i<n;i++){
if(grid[i][0]1 && !visited[i][0]) dfs(i,0,grid,visited);
if(grid[i][m-1]1 && !visited[i][m-1]) dfs(i,m-1,grid,visited);
}
for(int j=0;j<m;j++){
if(grid[0][j]1 && !visited[0][j]) dfs(0,j,grid,visited);
if(grid[n-1][j]1 && !visited[n-1][j]) dfs(n-1,j,grid,visited);
}
//将没有标记的陆地全部变成海洋
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(grid[i][j]1 && !visited[i][j]){
grid[i][j] = 0;
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cout << grid[i][j];
if(j!=m-1) cout << " ";
}
cout << endl;
}
return 0;
}