AOJ 0247 Ice Maze

問題

日本語なので本文参照。

制約条件

h, w≦12

方針

A*探索する。
コストのヒューリスティック値は、現在地からゴールまで、
氷のマスを自由に通れるとしたときの最短距離とする。
これは最初に前処理で求めておくことができる。

氷のマスは最初にunion-findして、つながりを見つけておく。

ソースコード

const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1};
const int inf = (int) 1e9;

int h, w, sy, sx, gy, gx;
string in[100];
set<pair<vi, int> > s;

int p[200], sz[200], size[200], dist[200][200];
int root(int x){ return x == p[x] ? x : (p[x] = root(p[x])); }

int main(){
	
	while(cin >> w >> h, w){
		rep(i, h){
			cin >> in[i];
			rep(j, w){
				if(in[i][j] == 'S') sy = i, sx = j;
				if(in[i][j] == 'G') gy = i, gx = j;
			}
		}
		
		rep(i, 200) p[i] = i, sz[i] = 1;
		rep(i, 200) rep(j, 200) dist[i][j] = inf;
		rep(i, h) rep(j, w) if(in[i][j] != '#'){
			rep(d, 4){
				int y = i + dy[d], x = j + dx[d];
				if(y < 0 || y >= h || x < 0 || x >= w) continue;
				if(in[y][x] != '#'){
					dist[i * w + j][y * w + x] = 1;
				}
			}
		}
		rep(k, 200) rep(i, 200) rep(j, 200)
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
		
		rep(i, h) rep(j, w) if(in[i][j] == 'X'){
			rep(d, 4){
				int y = i + dy[d], x = j + dx[d];
				if(y < 0 || y >= h || x < 0 || x >= w) continue;
				if(in[y][x] == 'X'){
					int a = root(y * w + x), b = root(i * w + j);
					if(a != b) p[b] = a, sz[a] += sz[b];
				}
			}
		}
		map<int, int> of;
		rep(i, h) rep(j, w) if(in[i][j] == 'X'){
			of[root(i * w + j)] = 0;
		}
		int k = 0;
		each(i, of){
			i->second = k++;
			size[i->second] = sz[i->first];
		}
		
		vi v(k);
		s.clear();
		priority_queue<pair<pi, pair<vi, int> > > q;
		
		q.push(mp(mp(-dist[gy * w + gx][sy * w + sx], 0), mp(v, sy * w + sx)));
		
		while(!q.empty()){
			int y = q.top().second.second / w, x = q.top().second.second % w;
			int c = q.top().first.second;
			v = q.top().second.first;
			q.pop();
			
			if(s.count(mp(v, y * w + x))) continue;
			s.insert(mp(v, y * w + x));
			
			if(in[y][x] == 'G'){
				cout << -c << endl;
				break;
			}
			
			rep(d, 4){
				int ny = y + dy[d], nx = x + dx[d];
				if(ny < 0 || ny >= h || nx < 0 || nx >= w || in[ny][nx] == '#') continue;
				vi nv = v;
				if(in[ny][nx] == 'X'){
					int t = of[root(ny * w + nx)];
					nv[t]++;
					if(2 * nv[t] > size[t]) continue;
				}
				q.push(mp(mp(-dist[gy * w + gx][ny * w + nx] + c, c - 1), mp(nv, ny * w + nx)));
			}
		}
	}
}