POJ 1077 - Eight

http://poj.org/problem?id=1077

概要

いわゆる15パズルと同じルールで，8枚の場合のパズルを解き，そのときの動かし方を答える (Special Judge)． ただし，解けない場合は「unsolvable」と答える．

制約

特になし

解法

A* 探索をする． ヒューリスティック関数には，最終的な状態とのマンハッタン距離の和を用いた．

盤面を string で持つと TLE だったが，配列として fixed_string で持ったら 563MS で通った．

 1 #include <iostream>
 2 #include <cstring>
 3 #include <map>
 4 #include <queue>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 struct fixed_string
 9 {
10   char buf[9];
11   fixed_string() {}
12   fixed_string(const fixed_string& s) { memcpy(buf, s.buf, 9); }
13   char& operator[](int n) { return buf[n]; }
14   char operator[](int n) const { return buf[n]; }
15   bool operator<(const fixed_string& s) const { return memcmp(buf, s.buf, 9) < 0; }
16 };
17 
18 int h(const fixed_string& s)
19 {
20   int d = 0;
21   for (int i = 0; i < 3; i++) {
22     for (int j = 0; j < 3; j++) {
23       const int x = s[3*i+j]-'1';
24       d += abs(x/3 - i) + abs(x%3 - j);
25     }
26   }
27   return d;
28 }
29 
30 bool finish(const fixed_string& s)
31 {
32   return h(s) == 0;
33 }
34 
35 fixed_string f(fixed_string s, int di, int dj)
36 {
37   for (int i = 0; i < 3; i++) {
38     for (int j = 0; j < 3; j++) {
39       char& t = s[3*i+j];
40       if (t == '9') {
41         const int k = i + di;
42         const int l = j + dj;
43         if (0 <= k && k < 3 && 0 <= l && l < 3) {
44           swap(t, s[3*k+l]);
45           return s;
46         } else {
47           return s;
48         }
49       }
50     }
51   }
52   throw "unexpected";
53 }
54 
55 int main()
56 {
57   fixed_string init;
58   for (int i = 0; i < 9; i++) {
59     char c;
60     cin >> c;
61     if (c == 'x') {
62       c = '9';
63     }
64     init[i] = c;
65   }
66 
67   priority_queue<pair<int,fixed_string> > q;
68   q.push(make_pair(-h(init), init));
69   map<fixed_string,string> dist;
70   dist.insert(make_pair(init, ""));
71   while (!q.empty()) {
72     const fixed_string s = q.top().second;
73     q.pop();
74     if (finish(s)) {
75       cout << dist[s] << endl;
76       return 0;
77     }
78     for (int d = 0; d < 4; d++) {
79       static const int di[] = {0, 0, -1, 1};
80       static const int dj[] = {1, -1, 0, 0};
81       const fixed_string t = f(s, di[d], dj[d]);
82       static const char tbl[] = "rlud";
83       const string cc = dist[s] + tbl[d];
84       const int hh = cc.size() + h(t);
85       if (!dist.count(t)) {
86         dist.insert(make_pair(t, cc));
87         q.push(make_pair(-hh, t));
88       }
89     }
90   }
91   cout << "unsolvable" << endl;
92   return 0;
93 }