POJ-3532, AOJ-1281 : The Morning after Halloween
問題概要
H*W(H,W<16)の2次元盤面上に3つの蟻と対応する3つのゴールがある。それぞれの蟻は独立に動けるが、同じマスに入ったり位置を交換することはできない。全ての蟻が対応するゴールに入るまでの時間の最小値を求める問題。解は存在することが保証されている。
解法
ゴールが一つ+遷移が双方向なので両側探索でも解けそうだったけどA*でやった。推定値はそれぞれのゴールへの距離の最大値とする。このときそれぞれが最も対応するゴールに近かったらそのまま終了判定してよい。
acceptされたコード
#include <cstdio> #include <queue> #include <cstring> #include <cctype> #include <algorithm> using namespace std; const int INF = 1000; const int MAX_W = 16; const int dy[] = {1,-1,0,0,0}, dx[] = {0,0,1,-1,0}; int W, H, N; int GY[3], GX[3], SY[3], SX[3]; char board[MAX_W][MAX_W + 1]; int distFromGoal[3][MAX_W][MAX_W]; unsigned short dist[MAX_W][MAX_W][MAX_W][MAX_W][MAX_W][MAX_W]; struct State { unsigned short dist; int y[3], x[3]; State(){} State(unsigned short dist, int y_[3], int x_[3]): dist(dist) { memcpy(y, y_, sizeof(y)); memcpy(x, x_, sizeof(x)); } }; bool operator> (const State& lhs, const State& rhs) { return lhs.dist > rhs.dist; } inline int getDist(int y0, int x0, int id) { return distFromGoal[id][y0][x0]; } inline int getDist(int y[3], int x[3]) { int ans = 0; for (int i = 0; i < N; ++i) { ans = max(ans, getDist(y[i], x[i], i)); } return ans; } bool init() { scanf("%d%d%d ", &W, &H, &N); for (int i = 0; i < H; ++i ) { scanf("%[^\n]%*c", board[i]); } return H > 0; } void dfs(int y[3], int x[3], int ny[3], int nx[3], int depth, int d, priority_queue<State, vector<State>, greater<State> > &que) { if (depth == N) { for (int i = 0; i < N; ++i) { for (int j = i + 1; j < N; ++j) { if (ny[i] == ny[j] && nx[i] == nx[j]) { return ; } if (y[i] == ny[j] && x[i] == nx[j] && y[j] == ny[i] && x[j] == nx[i]) { return ; } } } const int nd = d - getDist(y, x) + getDist(ny, nx) + 1; if (nd < dist[ny[0]][nx[0]][ny[1]][nx[1]][ny[2]][nx[2]]) { dist[ny[0]][nx[0]][ny[1]][nx[1]][ny[2]][nx[2]] = nd; que.push(State(nd, ny, nx)); } return ; } for (int k = 0; k < 5; ++k) { ny[depth] = y[depth] + dy[k], nx[depth] = x[depth] + dx[k]; if ( 0 <= ny[depth] && ny[depth] < H && 0 <= nx[depth] && nx[depth] < W && board[ny[depth]][nx[depth]] != '#') { dfs(y, x, ny, nx, depth + 1, d, que); } } } int solve() { memset(GY, 0, sizeof(GY)); memset(GX, 0, sizeof(GX)); memset(SY, 0, sizeof(SY)); memset(SX, 0, sizeof(SX)); for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { if (isupper(board[i][j])) { const int id = board[i][j] - 'A'; GY[id] = i; GX[id] = j; board[i][j] = ' '; } if (islower(board[i][j])) { const int id = board[i][j] - 'a'; SY[id] = i; SX[id] = j; board[i][j] = ' '; } } } for (int k = 0; k < N; ++k) { for (int i = 0; i < H; ++i) { fill(distFromGoal[k][i], distFromGoal[k][i] + W, INF); } } for (int i = 0; i < N; ++i) { queue<pair<int,int> > que; que.push(make_pair(GY[i], GX[i])); distFromGoal[i][GY[i]][GX[i]] = 0; for (;!que.empty();) { pair<int,int> tp = que.front(); que.pop(); const int y = tp.first, x = tp.second; for (int k = 0; k < 4; ++k) { const int ny = y + dy[k], nx = x + dx[k]; if ( 0 <= ny && ny < H && 0 <= nx && nx < W && board[ny][nx] != '#' && distFromGoal[i][ny][nx] == INF) { distFromGoal[i][ny][nx] = distFromGoal[i][y][x] + 1; que.push(make_pair(ny, nx)); } } } } memset(dist, ~0, sizeof(dist)); priority_queue<State, vector<State>, greater<State> > que; int initValue = getDist(SY, SX); que.push(State(initValue, SY, SX)); dist[SY[0]][SX[0]][SY[1]][SX[1]][SY[2]][SX[2]] = initValue; for (;!que.empty();) { State tp = que.top(); que.pop(); int y[3], x[3]; memcpy(y, tp.y, sizeof(y)); memcpy(x, tp.x, sizeof(x)); if (dist[y[0]][x[0]][y[1]][x[1]][y[2]][x[2]] < tp.dist) { continue; } { bool cut = true; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) if (i != j) { cut &= distFromGoal[i][y[i]][x[i]] < distFromGoal[i][y[j]][x[j]]; } } if (cut) { return int(tp.dist); } } int ny[3], nx[3]; memcpy(ny, tp.y, sizeof(ny)); memcpy(nx, tp.x, sizeof(nx)); dfs(y, x, ny, nx, 0, tp.dist, que); } return 0; } int main() { for (;init();) { printf("%d\n", solve()); } return 0; }