P9908 [COCI 2023/2024 #2] Pahuljice

xuan_gong_dong · 2023-12-29 19:35:11 · 题解

题面

P9908 [COCI 2023/2024 #2] Pahuljice

分析

看到数据范围 1 \le n,m \le 50，可以直接暴力解决，暴力枚举每一个节点是否为雪花的中心，如果是，暴力向八个方向拓展直到不合法，该节点为中心的雪花大小就是八个方向拓展长度的最小值。

然后就没了，时间复杂度是 n^3，随便过。

Code

#include<bits/stdc++.h>
using namespace std;
int nxt[8][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
char check[8]={'-','|','-','|',92,'/','/',92};
char c[100][100];
int n,m;
int Max;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",c[i]+1);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(c[i][j]=='+')
            {
                int Min=0x7f7f7f7f;
                for(int k=0;k<8;k++)
                {
                    int tx=i,ty=j;
                    int tmp=1;
                    while(c[tx+tmp*nxt[k][0]][ty+tmp*nxt[k][1]]==check[k])tmp++;
                    Min=min(Min,tmp-1);
                }
//              cout<<i<<' '<<j<<' '<<Min<<endl;
                Max=max(Max,Min);
            }
        }
    }
    printf("%d",Max);
    return 0;
}