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