自动搬运

查看原文

来自洛谷，原作者为

	Super_Cube AFO || 2020.09.20~2024.11.30 || 最后上线于 2024.12.31

搬运于2025-08-24 21:51:31，当前版本为作者最后更新于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;
}