程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 3690 Constellations 矩陣的hash

poj 3690 Constellations 矩陣的hash

編輯：C++入門知識

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
#include
#include
#include
#include
#include
#include
#include
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 s;
map ::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=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=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;
}