45.图论3

孤岛面积

#include<iostream>
using namespace std;
int N,M;
int quex[100000];
int quey[100000];
int hh=-1,tt=-1;
int gra[60][60];
int visited[60][60];
int res=0;
int dir[4][2]={0,1,0,-1,-1,0,1,0};
void bfs(int x,int y){hh=tt;tt++;quex[tt]=x;quey[tt]=y;while(hh<tt){int cur_x=quex[hh+1];int cur_y=quey[hh+1];for(int i=0;i<4;i++){int next_x=cur_x+dir[i][0];int next_y=cur_y+dir[i][1];if(next_x<0||next_y<0||next_x>=N||next_y>=M)continue;if(!visited[next_x][next_y]&&gra[next_x][next_y]){tt++;quex[tt]=next_x;quey[tt]=next_y;}}hh++;visited[cur_x][cur_y]=1;}
}int main(){scanf("%d%d",&N,&M);for(int i=0;i<N;i++){for(int j=0;j<M;j++){scanf("%d",&gra[i][j]);}}for(int i=0;i<N;i++){if(gra[i][0]&&!visited[i][0]){bfs(i,0);}if(gra[i][M-1]&&!visited[i][M-1]){bfs(i,M-1);}}for(int j=0;j<M;j++){if(gra[0][j]&&!visited[0][j]){bfs(0,j);}if(gra[N-1][j]&&!visited[N-1][j]){bfs(N-1,j);}}for(int i=0;i<N;i++){for(int j=0;j<M;j++){if(!visited[i][j]&&gra[i][j]){res++;}}}cout<<res;
}

沉没孤岛

#include<iostream>
using namespace std;
int N,M;
int quex[100000];
int quey[100000];
int hh=-1,tt=-1;
int gra[60][60];
int visited[60][60];
int res=0;
int dir[4][2]={0,1,0,-1,-1,0,1,0};
void bfs(int x,int y){hh=tt;tt++;quex[tt]=x;quey[tt]=y;while(hh<tt){int cur_x=quex[hh+1];int cur_y=quey[hh+1];for(int i=0;i<4;i++){int next_x=cur_x+dir[i][0];int next_y=cur_y+dir[i][1];if(next_x<0||next_y<0||next_x>=N||next_y>=M)continue;if(!visited[next_x][next_y]&&gra[next_x][next_y]){tt++;quex[tt]=next_x;quey[tt]=next_y;}}hh++;visited[cur_x][cur_y]=1;}
}int main(){scanf("%d%d",&N,&M);for(int i=0;i<N;i++){for(int j=0;j<M;j++){scanf("%d",&gra[i][j]);}}for(int i=0;i<N;i++){if(gra[i][0]&&!visited[i][0]){bfs(i,0);}if(gra[i][M-1]&&!visited[i][M-1]){bfs(i,M-1);}}for(int j=0;j<M;j++){if(gra[0][j]&&!visited[0][j]){bfs(0,j);}if(gra[N-1][j]&&!visited[N-1][j]){bfs(N-1,j);}}for(int i=0;i<N;i++){for(int j=0;j<M;j++){if(!visited[i][j]&&gra[i][j]){gra[i][j]=0;}}}for(int i=0;i<N;i++){for(int j=0;j<M;j++){printf("%d ",gra[i][j]);}printf("\n");}}

水流问题

#include<iostream>
using namespace std;
int g[110][110];
int visited_1[110][110];
int visited_2[110][110];
int N,M;
int dir[4][2]={0,1,0,-1,-1,0,1,0};
void dfs_1(int x,int y){visited_1[x][y]=1;for(int i=0;i<4;i++){int next_x=x+dir[i][0];int next_y=y+dir[i][1];if(next_x<0||next_y<0||next_x>=N||next_y>=M)continue;if(!visited_1[next_x][next_y]&&g[next_x][next_y]>=g[x][y]){dfs_1(next_x,next_y);}}
}
void dfs_2(int x, int y){visited_2[x][y]=1;if(visited_1[x][y]){printf("%d %d\n",x,y);}for(int i=0;i<4;i++){int next_x=x+dir[i][0];int next_y=y+dir[i][1];if(next_x<0||next_y<0||next_x>=N||next_y>=M)continue;if(!visited_2[next_x][next_y]&&g[next_x][next_y]>=g[x][y]){dfs_2(next_x,next_y);}}
}int main(){cin>>N>>M;for(int i=0;i<N;i++){for(int j=0;j<M;j++){scanf("%d",&g[i][j]);}}for(int i=0;i<N;i++){dfs_1(i,0);}for(int j=0;j<M;j++){dfs_1(0,j);}for(int i=0;i<N;i++){dfs_2(i,M-1);}for(int j=0;j<M;j++){dfs_2(N-1,j);}}

建造最大岛屿

# include<iostream>
using namespace std;
int g[60][60];
int visited[60][60];
int N,M;
int res_tmp=0;
int res=0;
int res_fin=0;
int dir[4][2]={0,1,0,-1,1,0,-1,0};void dfs(int x,int y){visited[x][y]=1;res_tmp++;for(int i=0;i<4;i++){int next_x=x+dir[i][0];int next_y=y+dir[i][1];if(next_x<0||next_y<0||next_x>=N||next_y>=M)continue;if(!visited[next_x][next_y]&&g[next_x][next_y]){dfs(next_x,next_y);}}
}int getres(){res=0;for(int i=0;i<N;i++){for(int j=0;j<M;j++){if(!visited[i][j]&&g[i][j]){res_tmp=0;dfs(i,j);res=max(res,res_tmp);}}}return 0;
} 
bool check(int x,int y){for(int i=0;i<4;i++){int next_x=x+dir[i][0];int next_y=y+dir[i][1];if(next_x<0||next_y<0||next_x>=N||next_y>=M)continue;if(g[next_x][next_y])return 1;}return 0;
}int main(){cin>>N>>M;bool all_zero=1;for(int i=0;i<N;i++){for(int j=0;j<M;j++){scanf("%d",&g[i][j]);if(g[i][j])all_zero=0;}}if(all_zero){cout<<1;return 0;}getres();res_fin=res;for(int i=0;i<N;i++){for(int j=0;j<M;j++){if(!g[i][j]&&check(i,j)){g[i][j]=1;getres();res_fin=max(res,res_fin);for(int n=0;n<N;n++){for(int m=0;m<M;m++){visited[n][m]=0;}}g[i][j]=0;}}}cout<<res_fin;}

这个是比较暴力的做法

# include<iostream>
using namespace std;
int g[60][60];
int visited[60][60];
int N,M;
int res_tmp=0;
int res=0;
int res_fin=0;
int dir[4][2]={0,1,0,-1,1,0,-1,0};
int Num[2510]={0};//记录下标对应岛屿编号的面积,从2开始用;
int idx=2;void dfs(int x,int y){visited[x][y]=1;res_tmp++;g[x][y]=idx;for(int i=0;i<4;i++){int next_x=x+dir[i][0];int next_y=y+dir[i][1];if(next_x<0||next_y<0||next_x>=N||next_y>=M)continue;if(!visited[next_x][next_y]&&g[next_x][next_y]){dfs(next_x,next_y);}}
}void getres(){res=0;for(int i=0;i<N;i++){for(int j=0;j<M;j++){if(!visited[i][j]&&g[i][j]){res_tmp=0;dfs(i,j);res=max(res,res_tmp);Num[idx]=res_tmp;idx++;}}}} 
int check(int x,int y){int tmp=0;int counted[4]={0,0,0,0};for(int i=0;i<4;i++){int next_x=x+dir[i][0];int next_y=y+dir[i][1];if(next_x<0||next_y<0||next_x>=N||next_y>=M)continue;if(g[next_x][next_y]==counted[0])continue;if(g[next_x][next_y]==counted[1])continue;if(g[next_x][next_y]==counted[2])continue;if(g[next_x][next_y]==counted[3])continue;tmp+=Num[g[next_x][next_y]];counted[i]=g[next_x][next_y];}return ++tmp;
}int main(){cin>>N>>M;bool all_zero=1;for(int i=0;i<N;i++){for(int j=0;j<M;j++){scanf("%d",&g[i][j]);if(g[i][j])all_zero=0;}}if(all_zero){cout<<1;return 0;}getres();for(int i=0;i<N;i++){for(int j=0;j<M;j++){if(!g[i][j]){res=max(res,check(i,j));}}}// for(int i=0;i<N;i++){//     for(int j=0;j<M;j++){//         printf("%d ",g[i][j]);//     }//     cout<<endl;// }// for(int i=2;i<idx;i++){//     cout<<Num[i]<<" ";// }cout<<res;}