Codeforces Round #102 (Div. 1) C : Help Caretaker

問題概要

T字型のペントミノをH*W(H,W<=9)に最大いくつ敷き詰められるか求める問題。実際に敷き詰めたものを出力する。

解法

2行覚えておくビットDPでもいけるけど復元がとても面倒。普通に探索する。分枝限定法で枝刈りできる。
また、この問題は最大独立集合だとみなすこともできる(ノード数9*9*4)。いつか最大独立集合ソルバができたら試してみたい。

acceptされたコード

#include <cstdio>
#include <cstring>
using namespace std;

const int MAX_W = 15;

const int dy[][5] = { {0,0,0,1,2}, {0,1,1,1,2}, {0,1,2,2,2}, {0,1,1,1,2}, };
const int dx[][5] = { {0,1,2,1,1}, {2,0,1,2,2}, {1,1,0,1,2}, {0,0,1,2,0}, };

int H, W;
char board[MAX_W][MAX_W + 1];
char best_board[MAX_W][MAX_W + 1];
int best_score, res, cur;

void init(){
	scanf("%d%d", &H, &W);
	for(int i=0; i<H; i++){
		for(int j=0; j<W; j++){
			board[i][j] = best_board[i][j] = '.';
		}
	}
}

inline bool can_put(int y, int x, int p){
	for(int k=0; k<5; k++){
		int ny = y + dy[p][k], nx = x + dx[p][k];
		if( !(0<=ny && ny<H && 0<=nx && nx<W && board[ny][nx]=='.') ){
			return false;
		}
	}
	return true;
}

inline void draw(int y, int x, int p, char col){
	for(int k=0; k<5; k++){
		int ny = y + dy[p][k], nx = x + dx[p][k];
		board[ny][nx] = col;
	}
}

void rec(int y, int x){
	if(x == W){
		if(y < H){
			rec(y+1, 0);
		}
		return ;
	}

	if(cur + res/5 <= best_score){
		return ;
	}

	if(y <= H-3 && x <= W-3){
		int tmp = res;
		for(int p=0; p<4; p++){
			if(can_put(y, x, p)){
				draw(y, x, p, 'A' + cur++);
				if(best_score < cur){
					best_score = cur;
					memcpy(best_board, board, sizeof(board));
				}
				res -= 5 + (board[y][x] == '.' ? 1 : 0);
				rec(y, x+1);
				res = tmp;
				cur--;
				draw(y, x, p, '.');
			}
		}
	}

	if(board[y][x] == '.'){
		res--;
	}
	rec(y, x+1);
	if(board[y][x] == '.'){
		res++;
	}
}

void solve(){
	cur = 0;
	res = H * W;
	rec(0, 0);
	printf("%d\n", best_score);
	for(int i=0; i<H; i++){
		puts(best_board[i]);
	}
}

int main(){

	init();
	solve();

	return 0;
}