読者です 読者をやめる 読者になる 読者になる

AOJ 1175 And Then. How Many Are There?

問題文: And Then. How Many Are There? | Aizu Online Judge

盤面の状態数は2^24である。それでDPすれば良い。ただ、AOJではcharじゃないとメモリオーバーになって死ぬ。

実装はDPよりメモ化再帰の方が効率的なのでそうした。

円と円の当たり判定は、

2つの円の中心の距離 < 半径1 + 半径2

が成り立てば当たっている。両辺を2乗してやると、整数で誤差のない当たり判定が実現できる。

追記(07/07):ビットの立ってる本数からいくつ除けたとか逆算できるので、それするとmemoはbool型で良くて、dfsは既にたどり着いた頂点かどうかでreturnするか決めるvoid型の関数で良い。(ansはグローバル変数にして関数内で更新する。)

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

int n;
int x[24],y[24],c[24],r[24];
char memo[1<<24];
int hit(int i,int j){
	int L = r[i]*r[i] + r[j]*r[j] + 2 * r[i] * r[j];
	int X = (x[i]-x[j])*(x[i]-x[j]);
	int Y = (y[i]-y[j])*(y[i]-y[j]);
	return X + Y < L;
}
int nocover(int n,int bit){
	for(int i = 0 ; i < n ; i++){
		if( (bit>>i&1) && hit(i,n) ) return false;
	}
	return true;
}
int dfs(int bit){
	if(~memo[bit]) return memo[bit];
	int ans = 0;
	for(int i = 0 ; i < n ; i++){
		for(int j = i+1 ; j < n ; j++){
			if( (bit >> j & 1) && (bit >> i & 1) && c[i] == c[j] && nocover(i,bit) && nocover(j,bit) ){
				ans = max(ans , dfs( bit & ~(1<<j) & ~(1<<i) ) + 2);
			}
		}
	}
	return memo[bit] = ans;
}
int main(){
	while(cin >> n , n){
		for(int i = 0 ; i < n ; i++){
			cin >> x[i] >> y[i] >> r[i] >> c[i];
		}
		memset(memo,-1,sizeof(memo));
		cout << dfs((1<<n)-1) << endl;
	}
}