AOJ 2380 Bubble Puzzle

問題

4x4のグリッド上に風船がおかれている。
風船には1〜4の数字がついている。

風船をクリックすると、風船の数字が1増える。
数字が5以上になった風船は、破裂して、上下左右の４方向に水滴が飛び散る。
割れた次の秒から、水滴は1秒に１マス進む。

水滴が別の風船につくと、ついたぶんだけ数字が増え、このときまた数字が5以上になると、
この風船が割れて連鎖反応がおきる。

何もないマスをクリックして、数字1の風船を作ることができる。
クリックは、前のクリックでおきた反応が完全に止まってからしかすることができない。

このとき、全ての風船を消すのにかかるクリックの回数の最小値を求めよ。
それが5回より多いときは-1を返せ。

制約条件

方針

幅優先探索。
そのままだとTLE, MLEになってしまうので、「今一番多い数字の風船を残りの回数クリックしても割れないならその時点で枝刈り」という処理を入れると0.2sくらいで終わるようになる。

ソースコード

const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1};
vector<vi> move(const vector<vi> &a, int y, int x, int co){
	vector<vi> b = a;
	int f[4][4] = {};
	
	if(++b[y][x] == 5){
		b[y][x] = 0;
		f[y][x] = (1 << 4) - 1;
	}
	while(1){
		bool update = 0;
		int pf[4][4];
		rep(i, 4) rep(j, 4) pf[i][j] = f[i][j], f[i][j] = 0;
		rep(i, 4) rep(j, 4) if(pf[i][j]){
			update = 1;
			rep(d, 4) if(pf[i][j] & 1 << d){
				int ny = i + dy[d], nx = j + dx[d];
				if(ny < 0 || nx < 0 || ny >= 4 || nx >= 4) continue;
				f[ny][nx] |= 1 << d;
			}
		}
		if(!update) break;
		rep(i, 4) rep(j, 4) if(b[i][j]){
			b[i][j] += __builtin_popcount(f[i][j]);
			if(b[i][j] >= 5){
				b[i][j] = 0;
				f[i][j] = (1 << 4) - 1;
			}
			else f[i][j] = 0;
		}
	}
	rep(i, 4) rep(j, 4) if(b[i][j]) return b;
	cout << co + 1 << endl;
	exit(0);
}

int main(){
	bool ng = 0;
	vector<vi> a(4, vi(4));
	rep(i, 4) rep(j, 4) cin >> a[i][j], ng |= a[i][j];
	queue<pair<int, vector<vi> > > q;
	set<vector<vi> > s;
	s.insert(a);
	q.push(mp(0, a));
	
	if(!ng){
		cout << 0 << endl;
		return 0;
	}
	
	while(!q.empty()){
		a = q.front().second;
		int co = q.front().first; q.pop();
		
		int mx = 0;
		rep(i, 4) rep(j, 4) mx = max(mx, a[i][j]);
		if(co > mx) continue;
		
		rep(i, 4) rep(j, 4){
			if(a[i][j] == 0){
				a[i][j] = 1;
				if(!s.count(a)){
					q.push(mp(co + 1, a));
					s.insert(a);
				}
				a[i][j] = 0;
			}
			else{
				vector<vi> b = move(a, i, j, co);
				if(co == 4 || s.count(b)) continue;
				s.insert(b);
				q.push(mp(co + 1, b));
			}
		}
	}
	cout << -1 << endl;
	
	return 0;
}