AOJ 1312 ICPC Asia resional 2010 Problem H: Where's Wally

問題

nxmマスの各マスが0または1のグリッドimageが与えられる。
pxpマスの各マスが0または1のグリッドpatternが与えられる。

imageの中にpatternはいくつ含まれるか求めよ。
patternが別の箇所に現れた場合、それらは別々にカウントする。
patternは上下左右の反転、90度単位の回転を何度してもよい。

制約条件

n,m≦1000
p≦100

方針

二次元でrolling hashを計算する。
imageの点(i,j)からpxpマスを切り取った部分のrolling hashと、patternのrolling hashが一致するかを見てやればよい。

ソースコード

int w,h,p;
ll hash[1001][1001],tmp[101][101],base[1001][1001];
bool img[1000][1000],ptn[100][100],ptn2[100][100];
char in[1001];

void mirror(){
	rep(i,p)rep(j,p/2)swap(ptn[i][j],ptn[i][p-1-j]);
}
void rot(){
	rep(i,p)rep(j,p)ptn2[i][j]=ptn[i][j];
	rep(i,p)rep(j,p)ptn[i][j]=ptn2[p-1-j][i];
}
inline int calcbit(char c){
	int bit;
	if('A'<=c&&c<='Z')bit=c-'A';
	else if('a'<=c&&c<='z')bit=c-'a'+26;
	else if('0'<=c&&c<='9')bit=c-'0'+52;
	else if(c=='+')bit=62;
	else if(c=='/')bit=63;
	else assert(0);
	return bit;
}

int main()
{
	base[0][0]=1;
	const ll tate=1000000007, yoko=7;
	rep(i,1000)rep(j,1000)if(i||j)
	base[i][j]=i?base[i-1][j]*tate:base[i][j-1]*yoko;
	
	while(scanf("%d%d%d ",&w,&h,&p),w){
		memset(img,0,sizeof(img));
		rep(i,h){
			fgets(in,1000,stdin);
			rep(j,(w-1)/6+1){
				int bit=calcbit(in[j]);
				rep(k,6)img[i][j*6+k]=bit&1<<5-k; //debug!!!
			}
		}
		rep(i,p){
			fgets(in,1000,stdin);
			rep(j,(p-1)/6+1){
				int bit=calcbit(in[j]);
				rep(k,6)ptn[i][j*6+k]=bit&1<<5-k;
			}
		}
		rep(i,h)rep(j,w){
			hash[i+1][j+1]=(img[i][j]+1)*base[i][j]+hash[i][j+1]+hash[i+1][j]-hash[i][j];
		}
		set<ll> patterns;
		rep(it,8){
			memset(tmp,0,sizeof(tmp));
			rep(i,p)rep(j,p){
				tmp[i+1][j+1]=(ptn[i][j]+1)*base[i][j]+tmp[i][j+1]+tmp[i+1][j]-tmp[i][j];
			}
			patterns.insert(tmp[p][p]);
			rot();
			if(it==3)mirror();
		}
		vector<ll> pattern(all(patterns));
		
		int ans=0;
		rep(i,h-p+1)rep(j,w-p+1){
			ll tmp=hash[i+p][j+p]-hash[i][j+p]-hash[i+p][j]+hash[i][j];
			rep(k,pattern.size()){
				ll tmp2=pattern[k]*base[i][j];
				if(tmp==tmp2)ans++;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}