题解 P5198 【[USACO19JAN]Icy Perimeter】

Polarnova · 2019-01-28 19:35:05 · 题解

可以不用搜索，考虑建立一个并查集，按顺序遍历并维护同一连通块的信息。
注意 合并点 和合并 点的信息 的顺序之类的细节。

#include<cstdio>
#include<iostream>

int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int n,tot,m[1003][1003],edge[1000009],fa[1000009],area[1000009],maxarea,minedge=0x3f3f3f3f;

int get(int x) {return ((x==fa[x])?x:fa[x]=get(fa[x]));}
void merge(int x,int y) {fa[get(x)]=get(y);}

int main() {
    scanf("%d\n",&n);
    char ch;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            scanf("%c",&ch);
            if(ch=='#')m[i][j]=++tot;
        }
        if(ch==EOF)break;
        getchar();
    }
    for(int i=1,n2=n*n;i<=n2;i++){fa[i]=i;area[i]=1;}
    for(int x=1;x<=n;x++) {
        for(int y=1;y<=n;y++) {
            if(m[x][y]==0)continue;
            for(int p=0;p<2;p++) {
                if(m[x+dx[p]][y+dy[p]]==0)continue;
                if(get(m[x+dx[p]][y+dy[p]])!=get(m[x][y])) {    
                    area[get(m[x][y])]+=area[get(m[x+dx[p]][y+dy[p]])];
                    edge[get(m[x][y])]+=edge[get(m[x+dx[p]][y+dy[p]])];
                    merge(m[x+dx[p]][y+dy[p]],m[x][y]);
                }
            }
            int edgex=4;
            for(int p=0;p<4;p++) if(m[x+dx[p]][y+dy[p]])edgex--;
            edge[get(m[x][y])]+=edgex;
            if(maxarea<area[get(m[x][y])]) {
                maxarea=area[get(m[x][y])];
                minedge=edge[get(m[x][y])];
            } else if(maxarea==area[get(m[x][y])]) {
                minedge=std::min(edge[get(m[x][y])],minedge);
            }
        }
    }
    printf("%d %d\n",maxarea,minedge);
    return 0;
}