AOJ 2146 Ninja Legend

AOJ 探索

問題

w x hのグリッドであらわされる部屋がある。
それぞれのマスは金塊が落ちているか、壁か、何もない床か、落とし穴のいずれかである。

忍者がスタートのマスからスタートして、金塊を回収する。
回収できる最大の金塊の数および、そのときの移動量の最小値を求めよ。


忍者は壁と落とし穴以外のマスを次のように動く。

  • 上下左右に隣接するに移動できる。
  • 上下左右方向に隣接して、落とし穴一つを飛び越えて移動できる。
  • ２マス、落とし穴でない床を移動すると、ダッシュモードになれる。
  • ダッシュモードのとき、２つの連続する落とし穴を飛び越えられる。
  • また、ダッシュモードのとき、壁を４歩まで歩くことができる。
  • 方向転換するか、壁を歩くか、金塊を拾うかすると通常モードに戻る。

制約条件

w, h≦80くらい
金塊の数は15個以下

方針

最初に金塊（とスタート）間の全点間最短距離を求める。
これは、それぞれの金塊（とスタート）を始点とするダイクストラをすれば求まる。
ノードは４方向にダッシュ中または通常モードの５通りに多重化する。


全点間最短距離が求まったら、ビットDPで巡回セールスマンを解けばいい。

ソースコード

const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1};
int h, w, gx[20], gy[20], m, dist[20][20];
string in[100];

inline bool wall(int y, int x, int d){
	y += dy[d]; x += dx[d];
	return in[y][x] == '#';
}
void calc(int sy, int sx, int s){
	static int dp[100][100][5];
	rep(i, h) rep(j, w) rep(k, 5) dp[i][j][k] = inf;
	priority_queue<pi> q;
	q.push(mp(0, (sy * w + sx) * 5 + 4));
	while(!q.empty()){
		int y = q.top().second / 5 / w, x = q.top().second / 5 % w;
		int dir = q.top().second % 5, c = q.top().first;
		q.pop();
		
		if(dp[y][x][dir] <= -c) continue;
		dp[y][x][dir] = -c;
		
		if(dir != 4){
			bool wallL = wall(y, x, dir + 1 & 3);
			bool wallR = wall(y, x, dir + 3 & 3);
			
			for(int k = 1; k <= 5; k++){
				int ny = y + k * dy[dir], nx = x + k * dx[dir];
				if(in[ny][nx] == '#') break;
				wallL &= wall(ny, nx, dir + 1 & 3);
				wallR &= wall(ny, nx, dir + 3 & 3);
				if((wallL || wallR) && in[ny][nx] != '^')
					q.push(mp(c - k, (ny * w + nx) * 5 + 4));
				if(k == 3 && in[ny][nx] != '^')
					q.push(mp(c - k, (ny * w + nx) * 5 + dir));
			}
		}
		rep(d, 4) for(int k = 1; k <= 2; k++){
			int ny = y + k * dy[d], nx = x + k * dx[d];
			if(in[ny][nx] == '#') break;
			bool dash = d == dir || k == 2 && in[ny - dy[d]][nx - dx[d]] != '^';
			if(in[ny][nx] != '^')
				q.push(mp(c - k, (ny * w + nx) * 5 + (dash ? d : 4)));
		}
	}
	rep(i, m){
		dist[s][i] = inf;
		rep(j, 5) dist[s][i] = min(dist[s][i], dp[gy[i]][gx[i]][j]);
	}
}
int main()
{
	while(cin >> h >> w, h){
		int sy, sx;
		m = 1;
		rep(i, h){
			cin >> in[i];
			rep(j, w){
				if(in[i][j] == '%') sy = i, sx = j;
				if(in[i][j] == '*') gy[m] = i, gx[m++] = j;
			}
		}
		gy[0] = sy; gx[0] = sx;
		rep(i, m) calc(gy[i], gx[i], i);
		
		static int dp[1<<16][16];
		int ans = 0, cost = 0;
		
		rep(i, 1 << m) rep(j, m) dp[i][j] = inf;
		dp[0][0] = 0;
		rep(i, 1 << m) rep(j, m) if(dp[i][j] != inf) rep(k, m)
			dp[i | 1 << k][k] = min(dp[i | 1 << k][k], dp[i][j] + dist[j][k]);
		
		rep(i, 1 << m) if(dp[i][0] != inf){
			int c = __builtin_popcount(i) - 1;
			if(c > ans || c == ans && cost > dp[i][0]) ans = c, cost = dp[i][0];
		}
		cout << ans << " " << cost << endl;
	}
	return 0;
}