AOJ 0243 Filling Game

問題

h x wのグリッドのそれぞれがR, G, Bのいずれかの色で塗られている。
(0, 0)のマスと、そこから上下左右に連続している同じ色のマス全てを、
R, G, Bののうち好きな色ひとつに変えるという操作が出来る。


グリッドの全てのマスを同じ色に変えるために必要な操作の回数の最小値を求めよ。

制約条件

h, w≦10

方針

探索。
(0, 0)の色を、今の色と同じ色へ変更する操作は意味がない。
なので、一回の操作は2通りで、最大手数はせいぜい20回くらいなので、
探索で十分間に合う。


以下の実装は適当に反復深化したものだけど、別に幅優先でもメモリが足りたかも。

ソースコード

const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1};
int h, w;
char in[20][20];
int lim;

void nul(int y, int x, char c, int *stk, int &m){
	char tmp = in[y][x];
	in[y][x] = c;
	stk[m++] = y * w + x;
	
	rep(d, 4){
		int ny = y + dy[d], nx = x + dx[d];
		if(ny < 0 || nx < 0 || ny >= h || nx >= w) continue;
		if(in[ny][nx] == tmp) nul(ny, nx, c, stk, m);
	}
}
bool rec(int s){
	
	char c = in[0][0];
	bool ok = 1;
	rep(i, h) rep(j, w) if(in[i][j] != c) ok = 0;
	if(ok) return 1;
	
	if(s >= lim) return 0;
	
	rep(i, 3) if(c != "RGB"[i]){
		int stk[100], m = 0;
		nul(0, 0, "RGB"[i], stk, m);
		if(rec(s + 1)) return 1;
		rep(j, m) in[stk[j] / w][stk[j] % w] = c;
	}
	return 0;
}

int main()
{
	while(cin >> w >> h, h){
		rep(i, h) rep(j, w) cin >> in[i][j];
		for(lim = 0; ; lim++){
			if(rec(0)) break;
		}
		cout << lim << endl;
	}
	return 0;
}