题解 P5198 【[USACO19JAN]Icy Perimeter】

YyunSu · 2019-09-14 20:27:59 · 题解

哇塞，好激动，AC了一道蓝题

在学校听大佬说这是一道纯搜索，于是我屁颠屁颠的做了一晚上，

没做出来，还好有大佬为我指明道路

在此感谢贞白徐晟，不要管大佬的名字颜色

看见好多大佬用广搜做，但是本蒟蒻自认为此题深搜更简洁易懂

话不多说，贴代码

#include <iostream>
#include <cstdio>
using namespace std;
char a[1005][1005];
int vis[1005][1005];
int dir[4][2] = {0,1,0,-1,1,0,-1,0}//方向数组，大佬们应该都知道吧...
int n,step = 0,step1 = 0;
int mmp (int r1, int r2) //不用在意函数名，不是我改的...qwq
{
    int k = 0;
    for (int w = 0; w < 4; w++){
        int xx = r1 + dir[w][0];
        int yy = r2 + dir[w][1];
        if (a[xx][yy] == '.') k++;
    }
    return k; 
} //求出上下左右“.”的数量，分开写更直观吧
void dfs(int x,int y) {
    vis[x][y] = step;//标记数组存步数，其实存什么无所谓...
    for(int i = 0; i < 4; i++) {
        int xx = x + dir[i][0];// 求上下左右的横坐标
        int yy = y + dir[i][1];//这个就是纵坐标喽
        if(xx >= 1 && xx <= n && yy >= 1 && yy <= n && !vis[xx][yy] && a[xx][yy] == '#') { // 判断边界以及是否被访问过
            step++;//存此时搜出来的冰淇淋大小
            step1 += mmp (xx, yy);//算一次四周的“.”的个数
            dfs(xx,yy);//递归走起
        }
    }
}
int main()
{
    int maxn = -9999,maxn1 = -9999;//一个存最大的冰淇淋的大小，另一个是“.”
    cin >> n;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 0; i <= n + 1; i++){
        a[0][i] = '.';
        a[n + 1][i] = '.';
        a[i][0] = '.';
        a[i][n + 1] = '.';
    }//灵魂代码，把周围的边界全部弄成"." 鸣谢徐大佬的提醒
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if (a[i][j] == '#'){
                step = 1;
                step1 = mmp (i, j);
                dfs(i,j);
                if(maxn < step) maxn = step, maxn1 = step1;//每出一个答案就要比一次，是不是最大
                if(maxn == step)
                    if (maxn1 > step1) maxn1 = step1; //同理 同上
            }   
        }
    }
    cout << maxn << ' '<< maxn1 <<endl;
    return 0;//完美结束（So beautiful!!!）
}

看完了的老爷们点个赞再走啊~~~