题解 P5198 【[USACO19JAN]Icy Perimeter】

· · 题解

题目不难，只用BFS就可以AC。第一次我开小了数组RE了（开的1001*1001，我也不知道为什么RE），第二次就AC了。实现不难。

BFS适用于向多个方向同时扩展，像这种在矩阵中求联通块的问题用BFS思维和代码难度都不高。用DFS多半也可以，但是我懒而且弱，故只写BFS。这类题有一个模板：求细胞数量。本题相对仅多一个求周长的步骤，也可以用裸BFS解决，还是比较水的。

具体实现上我建了三个数组用于BFS，见代码。求面积详见P1451。求周长时遍历每个点，看它周围有几个空格，并将空格数加入答案。

#include<bits/stdc++.h>
int n,max,ans,ax,ay,d=0x7fffffff,book[5001][5001],s[5001][5001],s1[5001][5001],step[5][3]={{0,0,0},{0,0,1},{0,1,0},{0,-1,0},{0,0,-1}};
std::queue<std::pair<int,int> > b;//STL
inline int find(int x,int y)
{
    int dis=0;
    s1[x][y]=0;
    b.push(std::make_pair(x,y));
    while(!b.empty())
    {
        int x1=b.front().first,y1=b.front().second;
        b.pop();
        for(register int i=1;i<=4;i=-~i)
            if(!s[x1+step[i][1]][y1+step[i][2]])
                dis=-~dis;//在此统计周长
        for(register int i=1;i<=4;i=-~i)
            if(s1[x1+step[i][1]][y1+step[i][2]])
            {
                s1[x1+step[i][1]][y1+step[i][2]]=0;
                b.push(std::make_pair(x1+step[i][1],y1+step[i][2]));
            }//同求面积函数的BFS
    }

    return dis;
}

inline void Breadth_First_Search(int x,int y)
{
    int res=0,f=find(x,y);//find求周长，这个函数主要负责求面积，顺便统计答案
    book[x][y]=0;
    b.push(std::make_pair(x,y));
    while(!b.empty())
    {
        int x1=b.front().first,y1=b.front().second;
        b.pop();
        res=-~res;
        for(register int i=1;i<=4;i=-~i)
        {
            if(book[x1+step[i][1]][y1+step[i][2]])
            {
                book[x1+step[i][1]][y1+step[i][2]]=0;
                b.push(std::make_pair(x1+step[i][1],y1+step[i][2]));
            }//step是扩展方向，这里向四个方向扩展并统计面积
        }
    }

    if(res>ans||!(res^ans)&&f<d)
    {
        ans=res;
        ax=x;
        ay=y;
        d=f;
    }//按题目的要求，求出最优解。f是前面求出的周长。

    return;
}

int main()
{
    scanf("%d",&n);
    for(register int i=1;i<=n;i=-~i)
        for(register int j=1;j<=n;j=-~j)
        {
            char c;
            scanf("%c",&c);
            while(c=='\n')
                scanf("%c",&c);
            s[i][j]=book[i][j]=s1[i][j]=!(c^'#')?1:0;//赋值，3个数组
        }

    for(register int i=1;i<=n;i=-~i)
        for(register int j=1;j<=n;j=-~j)
            if(book[i][j])
                Breadth_First_Search(i,j);//这里枚举每个点，对存在冰激凌的点进行BFS，并在BFS时删去本联通块
    printf("%d %d",ans,d);
    return 0;
}