JOI春合宿 2012-day1 JOI Flag

問題文 : 日本情報オリンピック旗

解法 :
旗を4つに分解し, それぞれに何を割り振るのかが最適なのかを深さ優先探索で決めていく.
ここで, 旗の大きさに対して最初から書かれている文字の個数が少ないので, 見ている範囲に文字が無い or 旗のレベルが0のときに探索を打ち切る.

コード :

#include <cstdio>
#include <algorithm>

int N;

int x[1024], y[1024], ch[1024];

using namespace std;

int dfs(int sx, int sy, int gx, int gy)
{
	int ct;
	int ans;
	int a[3];
	int s[4][3]; // J, O, I
	
	ct = 0;
	memset(s, 0, sizeof(s));
	for (int i = 0; i < N; i++){
		if (sx <= x[i] && x[i] <= gx && sy <= y[i] && y[i] <= gy){
			ct++;
		}
		if (sx <= x[i] && x[i] <= (sx + gx) / 2 && sy <= y[i] && y[i] <= (sy + gy) / 2){
			s[0][ch[i]]++;
		}
		if ((sx + gx) / 2 + 1 <= x[i] && x[i] <= gx && sy <= y[i] && y[i] <= (sy + gy) / 2){
			s[1][ch[i]]++;
		}
		if (sx <= x[i] && x[i] <= (sx + gx) / 2 && (sy + gy) / 2 + 1 <= y[i] && y[i] <= gy){
			s[2][ch[i]]++;
		}
		if ((sx + gx) / 2 + 1 <= x[i] && x[i] <= gx && (sy + gy) / 2 + 1<= y[i] && y[i] <= gy){
			s[3][ch[i]]++;
		}
	}
	if (ct == 0 || (sx == gx && sy == gy)) return (0);
	
	
	ans = 1024;
	
	for (int i = 0; i < 4; i++){
		if (i == 0) ct = dfs(sx, sy, (sx + gx) / 2, (sy + gy) / 2);
		if (i == 1) ct = dfs((sx + gx) / 2 + 1, sy, gx, (sy + gy) / 2);
		if (i == 2) ct = dfs(sx, (sy + gy) / 2 + 1, (sx + gx) / 2, gy);
		if (i == 3) ct = dfs((sx + gx) / 2 + 1, (sy + gy) / 2 + 1, gx, gy);
		a[0] = (i + 1) % 4, a[1] = (i + 2) % 4, a[2] = (i + 3) % 4;
		sort(a, a + 3);
		int p = 1024;
		do {
			int rJ = s[a[0]][1] + s[a[0]][2];
			int rO = s[a[1]][0] + s[a[1]][2];
			int rI = s[a[2]][0] + s[a[2]][1];
			p = min(p, rJ + rO + rI);
		} while (next_permutation(a, a + 3));
		ans = min(ans, ct + p);
	}
	
	return (ans);
}

int main()
{
	int K;
	
	scanf("%d %d", &K, &N);
	
	for (int i = 0; i < N; i++){
		char s[2];
		scanf("%d %d %s", &x[i], &y[i], s);
		
		switch (s[0]){
		  case 'J':
			s[0] = 0;
			break;
		  
		  case 'O':
		  	s[0] = 1;
			break;
		  
		  case 'I':
		  	s[0] = 2;
			break;
		}
		ch[i] = s[0];
	}
	
	printf("%d\n", dfs(1, 1, 1 << K, 1 << K));
}