字符串哈希
字符串哈希;如果两个矩阵哈希值相同,则这两个矩阵为同一个矩阵。
输入两个矩阵,设为st,ss;
先对ss求得哈希值(设为t),再分析可以发现一个矩阵可以旋转和翻转成八种矩阵(逆时针四种,顺时针四种),分别对八个矩阵求哈希值,如果其中一个矩阵哈希值等于t,则说明st和ss为同一个矩阵,如果八种都没有哈希值等于t,则是不同矩阵。
时间复杂度 O(n^2)
C++ 代码
#include<iostream>
#include<cstdio>
using namespace std;
const int N=110,P=131,M=12;
typedef unsigned long long ULL;
char st[N][N],ss[N][N];
int main(void)
{
int n;
scanf("%d",&n);
ULL t=0;
for(int i=1;i<=n;i++)
cin>>st[i]+1;
for(int i=1;i<=n;i++)
scanf("%s",ss[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
t=t*P+ss[i][j];
ULL res=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
res=res*P+st[i][j];
}
}
if(res==t)
{
printf("Yes");
return 0;
}
res=0;
for(int i=1;i<=n;i++)
{
for(int j=n;j>0;j--)
{
res=res*P+st[i][j];
}
}
if(res==t)
{
printf("Yes");
return 0;
}
res=0;
int m=n;
while(m)
{
int z=1;
for(int j=m--;z<=n;z++)
{
res=res*P+st[z][j];
}
}
if(res==t)
{
printf("Yes");
return 0;
}
res=0;
m=n;
while(m)
{
int z=n;
for(int j=m--;z>0;z--)
{
res=res*P+st[z][j];
}
}
if(res==t)
{
printf("Yes");
return 0;
}
res=0;
m=1;
while(m<=n)
{
int z=1;
for(int j=m++;z<=n;z++)
{
res=res*P+st[z][j];
}
}
if(res==t)
{
printf("Yes");
return 0;
}
res=0;
m=1;
while(m<=n)
{
int z=n;
for(int j=m++;z>0;z--)
{
res=res*P+st[z][j];
}
}
if(res==t)
{
printf("Yes");
return 0;
}
res=0;
for(int i=n;i>0;i--)
{
for(int j=n;j>0;j--)
{
res=res*P+st[i][j];
}
}
if(res==t)
{
printf("Yes");
return 0;
}
res=0;
for(int i=n;i>0;i--)
{
for(int j=1;j<=n;j++)
{
res=res*P+st[i][j];
}
}
if(res==t)
{
printf("Yes");
return 0;
}
printf("No");
return 0;
}