2091-Petoris

問題概要

置くブロックの形と現在の状況が与えられる．
ブロックを元々あるタイルと重ならないように回転などをして置いたとき，横一列が全てタイルで埋まる行な列は最大何個出来るか．

解法

全探索．
ビット演算を使うことで計算量を若干減らした．
1LL<<64に注意．

実装(C++)

#include <algorithm>
#include <vector>
#include <iostream>
#include <cstring>
using namespace std;

typedef unsigned long long int ull;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define rep(i,s,x) for(int i=s;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)

struct Block{
	int H,W;
	ull MAP[64];
	char data[64][64];
	void rotate(){
		ull cMAP[64];
		memcpy(cMAP,MAP,sizeof(ull)*64);
		REP(x,W){
			MAP[W-x-1]=0;
			REP(y,H){
				MAP[W-x-1]<<=1;
				MAP[W-x-1]+=(cMAP[y]>>(W-x-1))&1;
			}
		}
		swap(H,W);
	}
	void data2map(){
		for(int i=0;i<H;i++){
			MAP[i]=0;
			for(int x=0;x<W;x++){
				MAP[i]<<=1;
				MAP[i]+=data[x][i];
			}
		}
	}
	void clear(){
		int lx=99999,rx=-1,ty=99999,by=-1;
		char d[64][64];
		memcpy(d,data,sizeof(char)*64*64);
		REP(x,W){
			REP(y,H){
				if(data[x][y]){
					lx=min(lx,x);
					rx=max(rx,x);

					ty=min(ty,y);
					by=max(by,y);
				}
			}
		}
		if(lx==99999){
			H=W=0;
			return;
		}
		for(int x=lx;x<=rx;x++){
			for(int y=ty;y<=by;y++){
				data[x-lx][y-ty]=d[x][y];
			}
		}
		W=rx-lx+1;
		H=by-ty+1;
	}
};void show(Block &b ){
	cout<<"------"<<endl;
	REP(y,b.H){
		REP(x,b.W){
			if((b.MAP[y]>>x)&1){
				cout<<"#";
			}else{
				cout<<".";
			}
		}
		cout<<endl;
	}
}
istream &operator>>(istream &is,Block &bl){
	is>>bl.H>>bl.W;
	string tmp;
	REP(i,bl.H){
		cin>>tmp;
		REP(j,bl.W){
			if(tmp[j]=='#'){
				bl.data[j][i]=1;
			}else{
				bl.data[j][i]=0;
			}
		}
	}
	return is;
}
int solve(Block &tile,Block board,int x,int y){
	ull MASK=((unsigned long long)1)<<board.W;
	if(board.W==64)MASK=0;
	MASK-=1;

	for(int dy=0;dy<tile.H;dy++){
		if((board.MAP[dy+y]&(tile.MAP[dy]<<x))==0){
			board.MAP[dy+y]|=tile.MAP[dy]<<x;
		}else{
			return -1;
		}
	}
	int ans=0;
	REP(i,board.H){
		if(board.MAP[i]==MASK){
			ans++;
		}
	}
	return ans;
}
Block p[4];
int main(){
	int TCASE;
	for(cin>>TCASE;TCASE--;){
		Block a,b;
		cin>>a>>b;
		a.clear();
		a.data2map();
		b.data2map();
		REP(i,4){
			p[i]=a;
			a.rotate();
		}
		int ans=-1;
		REP(k,4){
			REP(x,b.W-p[k].W+1){
				REP(y,b.H-p[k].H+1){
					ans=max(ans,solve(p[k],b,x,y));
				}
			}
		}
		cout<<ans<<endl;
	}
}