2297-Rectangular Stamps

Rectangular Stamps | Aizu Online Judge

解法

最終状態から見ていく．
色が同じ部分に対して適当にスタンプを押し，その色を?に変える．
というのを繰り返すメモ化．
メモするのは?かどうかという情報のみで良い．

実装(C++)

#include <iostream>
using namespace std;
int N,H[20],W[20];
char MAP[4][4];
#define REP(i,x)for(int i=0;i<(int)x;i++)
int dp[1<<16];
int p2i(int a,int b){
	return a+b*4;
}
int solve(int used){
	int res=99999999;
	if(used==(1<<16)-1)return 0;
	if(dp[used]>=0)return dp[used];
	REP(k,N){
		for(int x=-W[k]+1;x<=3;x++){
			for(int y=-H[k]+1;y<=3;y++){
				bool ok=true;
				int next=used;
				int color=-1;
				for(int tx=x;tx<x+W[k];tx++){
					for(int ty=y;ty<y+H[k];ty++){
						if(tx<0||ty<0||tx>=4||ty>=4)continue;
						if((next>>p2i(tx,ty))&1)continue;
						if(color==-1){
							color=MAP[tx][ty];
						}
						if(MAP[tx][ty]!=color){
							ok=false;
							tx=9999;ty=9999;
							break;
						}else{
							next|=1<<p2i(tx,ty);
						}
					}
				}
				if(ok&&next!=used){
					res=min(res,solve(next)+1);
				}
			}
		}
	}
	return dp[used]=res;

}
int main() {
	cin>>N;
	REP(i,N){
		cin>>H[i]>>W[i];
	}
	for(int i=0;i<4;i++){
		string in;cin>>in;
		for(int j=0;j<4;j++){
			MAP[j][i]=in[j];
		}
	}
	fill(dp,dp+(1<<16),-1);
	cout<<solve(0)<<endl;
	return 0;
}