AOJ 0091 - Blur

問題文 : Blur

解法 :
基本的に枝刈り探索である.
・矛盾する状態(そこにインクを落とすと明らかに歪なインクの塊が残ってしまう)になったら探索をやめる
・インクの数を確定することが出来たら無闇にインクを落とすのをやめる
・探索に失敗したインクの集合をset にいれて, 同じ状態になってしまったら探索をやめる

上の2 つで18 ケースくらい通って, 最後のやつをやるとAC しました.
(ところで以下に示すようなコードを書く奴は腹を切って死ぬべきです.)

コード :

#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

int N;
int ax[13], ay[13], as[13];
int mp[12][12];
int size[3] = {3, 3, 5}, sz[3] = {5, 9, 13};
int exist[3];
int blur[3][5][5] = {{{0, 1, 0, 0, 0}, {1, 1, 1, 0, 0}, {0, 1, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}},
 	   				 {{1, 1, 1, 0, 0}, {1, 1, 1, 0, 0}, {1, 1, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}},
	      			 {{0, 0, 1, 0, 0}, {0, 1, 1, 1, 0}, {1, 1, 1, 1, 1}, {0, 1, 1, 1, 0}, {0, 0, 1, 0, 0}}};
bool finished;
bool isok[12][12];
void check(int, int);

set<vector<int> > ng;

bool check2(int n, int sum)
{
	memset(isok, 0, sizeof(isok));
	for (int x = 2; x >= 0; x--){
		for (int i = 0; i <= 10 - size[x]; i++){
			for (int j = 0; j <= 10 - size[x]; j++){
				//if (isok[i][j]) continue;
				for (int dy = 0; dy < size[x]; dy++){
					for (int dx = 0; dx < size[x]; dx++){
						if (mp[i + dy][j + dx] < blur[x][dy][dx]) goto na;
					}
				}
				
				for (int dy = 0; dy < size[x]; dy++){
					for (int dx = 0; dx < size[x]; dx++){
						isok[i + dy][j + dx] = 1;
					}
				}
				
				na:;
			}
		}
	}
	
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
			if (mp[i][j] != 0 && !isok[i][j]) return (false);
	
	if (exist[0] == -1){
		int ct = 0;
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= n - i; j++){
				if (5 * i + 9 * j + 13 * (n - (i + j)) == sum){
					ct++;
				}
			}
		if (ct == 0) return (false);
	}
	
	return (true);
}

void decr(int n, int x, int sum)
{
	if (finished) return;
	if (exist[x] != -1 && !exist[x]) return;
	
	for (int i = 0; i <= 10 - size[x]; i++){
		for (int j = 0; j <= 10 - size[x]; j++){
			
			for (int dy = 0; dy < size[x]; dy++){
				for (int dx = 0; dx < size[x]; dx++){
					if (mp[i + dy][j + dx] < blur[x][dy][dx]) goto next;
				}
			}
			for (int dy = 0; dy < size[x]; dy++){
				for (int dx = 0; dx < size[x]; dx++){
					mp[i + dy][j + dx] -= blur[x][dy][dx];
				}
			}
				
			if (check2(n - 1, sum - sz[x])){
				ax[n - 1] = j + (size[x] >> 1); ay[n - 1] = i + (size[x] >> 1); as[n - 1] = x + 1;
				if (~exist[x]) exist[x]--;
				check(n - 1, sum - sz[x]);
				if (~exist[x]) exist[x]++;
				ax[n - 1] = -1;
				if (finished) return;
			}
			
			for (int dy = 0; dy < size[x]; dy++){
				for (int dx = 0; dx < size[x]; dx++){
					mp[i + dy][j + dx] += blur[x][dy][dx];
				}
			}
			
			next:;
		}
	}
}
 
void check(int n, int sum)
{ 
	if (finished) return;
	vector<int> s;
	
	for (int i = N - 1; ~ax[i]; i--){
		s.push_back(ax[i] * 100 + ay[i] * 10 + as[i]);
	}
	sort(s.begin(), s.end());
	if (ng.count(s) != 0) return;
	
	if (n == 0){
		for (int i = 0; i < 10; i++)
			for (int j = 0; j < 10; j++)
				if (mp[i][j] != 0){
					ng.insert(s);
					return;
				}
				
		for (int i = 0; ~ax[i]; i++){
			printf("%d %d %d\n", ax[i], ay[i], as[i]);
	 	}
		finished = true;
		return;
	}
	
	if (exist[0] == -1){
		int ct = 0;
		int cand[3];
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= n - i; j++){
				if (5 * i + 9 * j + 13 * (n - (i + j)) == sum){
					cand[0] = i; cand[1] = j; cand[2] = n - (i + j);
					ct++;
				}
			}
		if (ct == 0){
			ng.insert(s);
			return;
		}
		
		if (ct == 1){
			exist[0] = cand[0]; exist[1] = cand[1]; exist[2] = cand[2];
		}
	}
	
	for (int i = 2; i >= 0; i--){
		decr(n, i, sum);
		if (finished) return;
	}
	
	exist[0] = exist[1] = exist[2] = -1;
	ng.insert(s);
}

int main()
{
	int n, sum = 0;
	scanf("%d", &n);
	
	N = n;
	for (int i = 0; i < 10; i++){
		for (int j = 0; j < 10; j++){
			scanf("%d", &mp[i][j]);
			sum += mp[i][j];
		}
	}
	memset(exist, -1, sizeof(exist));
	memset(ax, -1, sizeof(ax));
	check(n, sum);
	return (0);
}