首页 > 代码库 > poj 3690 Constellations 矩阵的hash
poj 3690 Constellations 矩阵的hash
给定一个n*m矩阵和t个p*q的矩阵,求这t个矩阵有多少个是n*m的子矩阵。
矩阵都是01矩阵,只有‘0‘ ‘*‘
矩阵的hash,先将每行q列hash,得到一个新矩阵,然后再每列p行hash 【注意行列hash时候取的magic数不能一样,不然很容易冲突,会WA,最好取2个素数】
这样原矩阵的每个子矩阵都由一个数字代替了,之后用map判断就够了。
注意:不能事先将原矩阵的所有子矩阵hash值存在map里,然后比较,由于子矩阵数量太大会MLE。
map里存的应该是t个矩阵的hash值,注意有重复的矩阵,次数还是要加上。
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<algorithm> #include<map> #include<set> #include<iterator> using namespace std; typedef unsigned long long ull; int ba=131; int ba2=499; char mp[1005][1005]; char a[100][100]; ull H[1005]; ull xp[1005]; ull xp2[1005]; ull nmp[1005][1005]; map<ull,int> s; map<ull,int> ::iterator it; int n,m,t,q,p,ca=1; int main() { xp2[0]=xp[0]=1; for(int i=1;i<=1001;i++) xp[i]=xp[i-1]*ba,xp2[i]=xp2[i-1]*ba2; while(~scanf("%d%d%d%d%d",&n,&m,&t,&p,&q)) { if(n+m+t+p+q==0) break; s.clear(); int ans=0; for(int i=0;i<n;i++) scanf("%s",mp[i]); while(t--) { for(int i=0;i<p;i++) scanf("%s",a[i]); ull tmp; for(int i=0;i<p;i++) { tmp=0; for(int j=q-1;j>=0;j--) tmp=tmp*ba+a[i][j]; H[i]=tmp; } tmp=0; for(int i=p-1;i>=0;i--) tmp=tmp*ba2+H[i]; s[tmp]++; } for(int i=0;i<n;i++) { H[m]=0; for(int j=m-1;j>=0;j--) H[j]=H[j+1]*ba+mp[i][j]; for(int j=0;j+q<=m;j++) nmp[i][j]=H[j]-H[j+q]*xp[q]; } for(int j=0;j+q<=m;j++) { H[n]=0; for(int i=n-1;i>=0;i--) H[i]=H[i+1]*ba2+nmp[i][j]; for(int i=0;i+p<=n;i++) { it=s.find(H[i]-H[i+p]*xp2[p]); if(it!=s.end()) { ans+=it->second; s.erase(it); } } } printf("Case %d: %d\n",ca++,ans); } return 0; }
poj 3690 Constellations 矩阵的hash
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。