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))); } } } }