Codeforces 375(#221 Div1) C. Circling Round Treasures

問題

２次元のグリッドが与えられる。
Sはスタート。.は何もないマス。数字は宝の番号で、#は壁でBは爆弾。
SからスタートしてSまで戻ってくる閉路（同じマスを二回以上通ってもよい）で、宝を囲いたい。

閉路の長さをvとして、囲った宝の価値の総和をwとすると、
スコアはw - vである。スコアの最大値を求めよ。
ただし、爆弾を囲うと死ぬ。

閉路が物体を囲うとは、物体から半直線を伸ばしたとき、閉路と交わる回数が奇数回であることを言う。

制約条件

幅, 高さ≦20
宝と爆弾の個数の和≦8

方針

爆弾はスコアマイナス無限の宝としてよい。
宝ごとにy軸の上方向に半直線を引いて、これとの交わる回数を考える。

(位置, i番目の宝から伸びる半直線と奇数回交わっているかのmask)を状態として、
幅優先探索をすれば、スタートに戻ってきているときに、スコアが求まる。
（奇数回交わってる宝の価値の和 - 歩数）

マスクの増やし方が難しくて、
x座標が増えたときは移動先のmaskを足す、
x座標が減ったときは移動前のmaskを足す、とすると上手く行く。
（昔、夏合宿の京大の魔女セットで平面走査の問題で似たようなことやったような記憶も…）

ソースコード

直前の方向に戻るのを禁止したけど別になくても正しい答えが出るので意味なかった。

int h, w, n, a[20], mask[20][20];
string in[20];

bool v[5][400][1 << 8];

int main(){
	int sx, sy;
	cin >> h >> w;
	rep(i, h){
		cin >> in[i];
		rep(j, w){
			if(isdigit(in[i][j])){
				rep(k, i + 1) mask[k][j] |= 1 << in[i][j] - '1';
				n++;
			}
			if(in[i][j] == 'S'){
				sy = i, sx = j;
				in[i][j] = '.';
			}
		}
	}
	rep(i, n) cin >> a[i];
	rep(i, h) rep(j, w) if(in[i][j] == 'B'){
		rep(k, i + 1) mask[k][j] |= 1 << n;
		a[n++] = -100000;
	}
	/*
	rep(i, h) rep(j, w) cerr<<mask[i][j]<<(j==w-1?"\n":" ");
	rep(i, h) dbg(in[i]);
	*/
	int ans = 0;
	queue<pair<pi, pi> > q; //(cost, prev, pos, bit)
	q.push(mp(mp(0, 4), mp(sy * w + sx, 0)));
	
	while(!q.empty()){
		int y = q.front().second.first / w, x = q.front().second.first % w;
		int bit = q.front().second.second;
		int cost = q.front().first.first, prev = q.front().first.second; q.pop();
		
		//cerr<<"y: "<<y<<" x: "<<x<<endl;
		
		if(v[prev][y * w + x][bit]) continue;
		v[prev][y * w + x][bit] = 1;
		
		if(y == sy && x == sx){
			int score = cost;
			rep(i, n) if(bit & 1 << i) score += a[i];
			ans = max(ans, score);
		}
		
		rep(d, 4){
			const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1};
			int ny = y + dy[d], nx = x + dx[d];
			if(ny < 0 || nx < 0 || ny >= h || nx >= w || in[ny][nx] != '.') continue;
			if(prev < 4 && dy[prev] + dy[d] == 0 && dx[prev] + dx[d] == 0) continue;
			
			int nbit = bit;
			if(d == 3) nbit ^= mask[y][x];
			if(d == 1) nbit ^= mask[ny][nx];
			q.push(mp(mp(cost - 1, d), mp(ny * w + nx, nbit)));
		}
	}
	cout << ans << endl;
	return 0;
}