AOJ 0132 Jigsaw Puzzle

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0132）

制約条件

パズルの幅, 高さ≦20
ピースの個数≦10
各ピースの幅, 高さ≦20

方針

枝刈り探索。
割と自明な枝刈りだけで通る。

まずは、使うピースを大きい順に並べたほうがよさそうなので、大きい順に並べる。
（本当かどうかは未検証）

で、ピースを順番に置いていくことを試すのだが、
空いてるマスのうち、まだ使っていないピースをどのように置いても埋まらないマスがあったとしたら、そのような置き方は絶対に失敗するので、枝刈りする。
これだけで通った。

ソースコード

int H, W, n, h[40], w[40], sz[40];
int m, no[10];
char in[20][21], pc[40][20][21];
bool v[20][20], u[20][20];

bool cmp(int a, int b){
	return sz[a] > sz[b];
}
bool rec(int c){
	if(c == m) return 1;
	memset(u, 0, sizeof(u));
	rep(i, H) rep(j, W) if(in[i][j] == '.' && !u[i][j]){
		for(int k = c; k < m; k++) rep(t, 4){
			int p = no[k] + t * n;
			for(int y = max(0, i - h[p] + 1); y <= i && y + h[p] <= H; y++)
			for(int x = max(0, j - w[p] + 1); x <= j && x + w[p] <= W; x++){
				rep(a, h[p]) rep(b, w[p]){
					if(pc[p][a][b] == '#' && in[y + a][x + b] == '#') goto FAIL;
				}
				rep(a, h[p]) rep(b, w[p]){
					if(pc[p][a][b] == '#') u[y + a][x + b] = 1;
				}
				FAIL:;
			}
		}
		if(!u[i][j]) return 0;
	}
	rep(t, 4){
		int p = no[c] + t * n;
		for(int y = 0; y + h[p] <= H; y++)
		for(int x = 0; x + w[p] <= W; x++){
			bool ok = 1;
			rep(a, h[p]) rep(b, w[p]) if(in[y + a][x + b] == '#' && pc[p][a][b] == '#') ok = 0;
			if(ok){
				rep(a, h[p]) rep(b, w[p]) if(pc[p][a][b] == '#') in[y + a][x + b] = '#';
				bool res = rec(c + 1);
				rep(a, h[p]) rep(b, w[p]) if(pc[p][a][b] == '#') in[y + a][x + b] = '.';
				if(res) return 1;
			}
		}
	}
	return 0;
}

int main()
{
	while(cin >> H >> W, H){
		int sp = 0;
		rep(i, H){
			cin >> in[i];
			rep(j, W) if(in[i][j] == '.') sp++;
		}
		
		cin >> n;
		
		rep(i, n){
			cin >> h[i] >> w[i];
			
			sz[i] = 0;
			rep(j, h[i]){
				cin >> pc[i][j];
				rep(k, w[i]) if(pc[i][j][k] == '#') sz[i]++;
			}
			
			int s = i;
			rep(j, 3){
				int t = s + n;
				
				h[t] = w[s];
				w[t] = h[s];
				sz[t] = sz[s];
				
				rep(y, h[s]) rep(x, w[s])
					pc[t][x][h[s] - y - 1] = pc[s][y][x];
				s = t;
			}
		}
		int q;
		cin >> q;
		while(q--){
			cin >> m;
			int sum = 0;
			rep(i, m) cin >> no[i], sum += sz[--no[i]];
			sort(no, no + m, cmp);
			
			memset(v, 0, sizeof(v));
			cout << (sum == sp && rec(0) ? "YES" : "NO") << endl;
		}
	}
	return 0;
}