P3678 [CERC2016] 外观分析 Appearance Analysis

Super_Cube · 2024-11-06 22:06:22 · 题解

Solution

求出每个窗户的横纵边长，然后将窗户内的样子进行哈希。算哈希的方法就正常打字符串哈希，不过要在换行处补上一个空字符把两行隔开。有点烦人的地方是窗户可以旋转，所以每个窗户会算出四个哈希值，要全部判断一遍才知道是否已经和前面的某个窗户重复了。没重复就把哈希值放入桶中，最后的答案即为桶中元素数量。

Code

#include<bits/stdc++.h>
typedef unsigned long long ull;
const ull P=173;
std::unordered_set<ull>mp;
char s[150][150];
int n,m,p,q;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;scanf("%s",s[i++]));
    for(int i=0;i<n;++i)p+=s[i][1]=='#';
    for(int i=0;i<m;++i)q+=s[1][i]=='#';
    p=(n-p)/(p-1);q=(m-q)/(q-1);
    for(int i=1;i<n;i+=p+1)
        for(int j=1;j<m;j+=q+1){
            static ull hash1,hash2,hash3,hash4;
            hash1=hash2=hash3=hash4=0;
            for(int x=0;x<p;++x){
                hash1=hash1*P+54;
                for(int y=0;y<q;++y)
                    hash1=hash1*P+s[i+x][j+y];
            }
            for(int x=p-1;~x;--x){
                hash2=hash2*P+54;
                for(int y=q-1;~y;--y)
                    hash2=hash2*P+s[i+x][j+y];
            }
            for(int y=q-1;~y;--y){
                hash3=hash3*P+54;
                for(int x=0;x<p;++x)
                    hash3=hash3*P+s[i+x][j+y];
            }
            for(int y=0;y<q;++y){
                hash4=hash4*P+54;
                for(int x=p-1;~x;--x)
                    hash4=hash4*P+s[i+x][j+y];
            }
            if(!mp.count(hash1)&&!mp.count(hash2)&&!mp.count(hash3)&&!mp.count(hash4))
                mp.insert(hash1);
        }
    printf("%d",mp.size());
    return 0;
}