POJ-2046 : Gap

問題概要

15パズル風に空きマスに数字を移動させるゲームがある(ルールの詳細は略)。クリアできるのであれば最短手数を求める。無理なら指摘する。

解法

幅優先探索で間に合うらしい。状態の合流があるとはいえ意外。
以下の自分の実装では盤面をcharで圧縮して持ったりして高速化したり、異なる位置に収まっていないタイルの個数を下限にとってA*しているけど、後者はやらない方がよい。なぜなら解を持たないケースがあって、そのときにはまったく役に立たないどころかpriority_queueの操作の分だけ処理が重くなるから。最悪ケースでどうなるかが大事。とはいえ実際のテストケースは多分そんなに-1のケース入ってないと思うけど。

追記

A*についての理解を間違えていた。やっぱり普通に幅優先した方がよい…。

acceptされたコード

#include <cstdio>
#include <queue>
#include <algorithm>
#include <map>
#include <cstring>
using namespace std;

struct Board {
	char state[4][8];
	Board(){}
};

bool operator< (const Board& lhs, const Board& rhs) {
	return memcmp(&lhs, &rhs, sizeof(Board)) < 0;
}

int board[4][8];

void init() {
	memset(board, 0, sizeof(board));
	for (int i = 0; i < 4; ++i) {
		for (int j = 0; j < 7; ++j) {
			scanf("%d", board[i]+j+1);
		}
	}
}

int estimateBoard(const Board& x) {
	int ans = 0;
	for (int i = 0; i < 4; ++i) {
		for (int j = 0; j < 8; ++j) if (x.state[i][j] != -1) {
			if (!((x.state[i][j]>>3) == i && (x.state[i][j]&7) == j)) {
				++ans;
			}
		}
	}
	return ans;
}

int solve() {
	map<Board, int> estimate;
	
	priority_queue< pair<int, Board> > que;

	Board start;
	memset(&start.state, -1, 4*8);
	for (int i = 0; i < 4; ++i) {
		for (int j = 1; j < 8; ++j) {
			if (board[i][j]) {
				start.state[i][j] = ((board[i][j]/10 - 1)<<3) | (board[i][j]%10 - 1);
			}
			if ((start.state[i][j]&7) == 0) {
				swap(start.state[start.state[i][j]>>3][0], start.state[i][j]);
			}
		}
	}
	estimate[start] = estimateBoard(start);
	que.push(make_pair(-estimate[start], start));

	for (;!que.empty();) {
		int dist = -que.top().first;
		Board cur = que.top().second;
		que.pop();

		int esti = estimate[cur];
		if (esti == 0) {
			return dist;
		}
		dist -= esti;

		for (int i = 0; i < 4; ++i) {
			for (int j = 1; j < 8; ++j) if (cur.state[i][j] == -1) {
				char left = cur.state[i][j-1] + 1;
				for (int ii = 0; ii < 4; ++ii) {
					for (int jj = 1; jj < 8; ++jj) if (cur.state[ii][jj] == left) {
						swap(cur.state[ii][jj], cur.state[i][j]);
						if (estimate.find(cur) == estimate.end()) {
							estimate[cur] = estimateBoard(cur);
							int nd = dist + 1 + estimate[cur];
							que.push(make_pair(-nd, cur));
						}
						swap(cur.state[ii][jj], cur.state[i][j]);
					}
				}
			}
		}
	}

	return -1;
}

int main() {
	int T; scanf("%d", &T);
	for (int _ = 0; _ < T; ++_) {
		init();
		printf("%d\n", solve());
	}
	return 0;
}