模板题、floodfill求四连块

1、棋盘数据存储

　　int a[1005][1005];
　　a[i][j]=1 表示巧克力块，a[i][j]=0 表示空。

　　scanf("%d",&N);
　　string s;
　　for(int i=1;i<=N;i++)
　　{
　　　　cin>>s;
　　　　for(int j=1;j<=N;j++)
　　　　if(s[j-1]=='#') a[i][j]=1;

　　}

2、BFS找四连块

　　struct D{ int x,y;};
　　int dx[5]={-1,1,0,0};
　　int dy[5]={0,0,-1,1};
　　int N,a[1005][1005],S,C,Anss,Ansc;
　　bool v[1005][1005];   //标记是否访问过

　　void BFS(int x,int y){
　　　　queue<D>q;
　　　　q.push((D){x,y});
　　　　v[x][y]=true;
　　　　while(!q.empty()){
　　　　　D t=q.front(); q.pop();
　　　　　S++;                            //四连块面积增加1
　　　　　for(int i=0;i<4;i++){
　　　　　　　tt.x=t.x+dx[i],tt.y=t.y+dy[i];
　　　　　　　if(a[tt.x][tt.y]==0) C++;   //四连块周长增加1
　　　　　　　if(!v[tt.x][tt.y] && a[tt.x][tt.y]==1){
　　　　　　　　　q.push(tt);
　　　　　　　　　v[tt.x][tt.y]=true;
　　　　　　　　}
　　　　　　}
　　　　}
　　}

3、调用

　　for(int i=1;i<=N;i++)
　　for(int j=1;j<=N;j++)
　　　　if(!v[i][j]&&a[i][j]){
　　　　　　S=C=0;
　　　　　　BFS(i,j);
　　　　　　if(S>Anss) 
　　　　　　　　Anss=S,Ansc=C;
　　　　　　else if(S==Anss && C<Ansc)
　　　　　　　　Ansc=C;
　　}

附录：DFS求四连块

　　void DFS(int x,int y){
　　　　S++;
　　　　v[x][y]=true;
　　　　for(int i=0;i<4;i++){
　　　　　　int xx=x+dx[i],yy=y+dy[i];
　　　　　　if(a[xx][yy]==0) C++;
　　　　　　if(!v[xx][yy] && a[xx][yy]==1) 
　　　　　　　　DFS(xx,yy);
　　　　}
　　}