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