HDU 1043 Eight(A*+HASH+康托展開)
31032 ワード
Eight
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 13956 Accepted Submission(s): 3957 Special Judge
Problem Description
The 15-puzzle has been around for over 100 years; even if you don't know it by that name, you've seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. Let's call the missing tile 'x'; the object of the puzzle is to arrange the tiles so that they are ordered as:
Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing 'x' tile, of course).
In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three arrangement.
Input
You will receive, several descriptions of configuration of the 8 puzzle. One description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus 'x'. For example, this puzzle
1 2 3 x 4 6 7 5 8
is described by this list:
1 2 3 x 4 6 7 5 8
Output
You will print to standard output either the word ``unsolvable'', if the puzzle has no solution, or a string consisting entirely of the letters 'r', 'l', 'u' and 'd' that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line. Do not print a blank line between cases.
Sample Input
2 3 4 1 5 x 7 6 8
Sample Output
ullddrurdllurdruldr
この問題は生々しく5日間やったので、A*とコントの展開を学んだ.自分で書いたが、まだよく分からない.「もしあなたが本当に知っていたら、自分で作るべきだ」という言葉があったが、私はまだ本当に理解していないようだ.
まず各行列の構造を構造に格納し,次に行列全体をカント展開でハッシュし,このような状況が現れたか,あるいは終点に達したかを判断する値を得た.したがって,初期の場合の逆序数が奇数であれば不可解である.
分からないところはA*の評価関数がなぜf=g+hではなく、hとgをそれぞれ2つのパラメータとして比較するのか、最初は2つのパラメータの位置を逆にして、1日Tしました.涙ばかりです.
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 13956 Accepted Submission(s): 3957 Special Judge
Problem Description
The 15-puzzle has been around for over 100 years; even if you don't know it by that name, you've seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. Let's call the missing tile 'x'; the object of the puzzle is to arrange the tiles so that they are ordered as:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 x 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8 9 x 10 12 9 10 x 12 9 10 11 12 9 10 11 12 13 14 11 15 13 14 11 15 13 14 x 15 13 14 15 x r-> d-> r->Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing 'x' tile, of course).
In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three arrangement.
Input
You will receive, several descriptions of configuration of the 8 puzzle. One description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus 'x'. For example, this puzzle
1 2 3 x 4 6 7 5 8
is described by this list:
1 2 3 x 4 6 7 5 8
Output
You will print to standard output either the word ``unsolvable'', if the puzzle has no solution, or a string consisting entirely of the letters 'r', 'l', 'u' and 'd' that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line. Do not print a blank line between cases.
Sample Input
2 3 4 1 5 x 7 6 8
Sample Output
ullddrurdllurdruldr
この問題は生々しく5日間やったので、A*とコントの展開を学んだ.自分で書いたが、まだよく分からない.「もしあなたが本当に知っていたら、自分で作るべきだ」という言葉があったが、私はまだ本当に理解していないようだ.
まず各行列の構造を構造に格納し,次に行列全体をカント展開でハッシュし,このような状況が現れたか,あるいは終点に達したかを判断する値を得た.したがって,初期の場合の逆序数が奇数であれば不可解である.
分からないところはA*の評価関数がなぜf=g+hではなく、hとgをそれぞれ2つのパラメータとして比較するのか、最初は2つのパラメータの位置を逆にして、1日Tしました.涙ばかりです.
1 #include <iostream>
2 #include <cmath>
3 #include <string>
4 #include <queue>
5 #include <cstdio>
6 #include <cstring>
7 #include <algorithm>
8 using namespace std;
9
10 const int SIZE = 5;
11 const int GOAL = 46233;
12 const int HASH[] = {40320,5040,720,120,24,6,2,1,1};
13 const int UP_DATE[][2] = {{0,-1},{0,1},{-1,0},{1,0}};
14 int PATH[600000];
15 int PRE[600000];
16 struct Node
17 {
18 int map[SIZE][SIZE];
19 int x,y;
20 int h,g;
21 int hash;
22 bool operator <(const Node a) const
23 {
24 return h != a.h ? h > a.h : g > a.g;
25 }
26 };
27
28 bool solve_able(const Node & r);
29 bool check(const int,const int);
30 void cal_hash(Node & r);
31 void cal_h(Node & r);
32 void search(const Node & r);
33 void show(void);
34 int main(void)
35 {
36 Node first;
37 char s[50];
38
39 while(gets(s))
40 {
41 int k = 0;
42 memset(PRE,-1,sizeof(PRE));
43 memset(PATH,-1,sizeof(PATH));
44 for(int i = 1;i <= 3;i ++)
45 for(int j = 1;j <= 3;j ++)
46 {
47 if(s[k] >= '1' && s[k] <= '9')
48 first.map[i][j] = s[k] - '0';
49 else if(s[k] == 'x')
50 {
51 first.map[i][j] = 0;
52 first.x = i;
53 first.y = j;
54 }
55 else
56 j --;
57 k ++;
58 }
59 if(!solve_able(first))
60 {
61 printf("unsolvable
");
62 continue;
63 }
64 cal_hash(first);
65 if(first.hash == GOAL)
66 {
67 puts("");
68 continue;
69 }
70 PATH[first.hash] = -2;
71 first.g = 0;
72 cal_h(first);
73 search(first);
74 }
75
76 return 0;
77 }
78
79 bool solve_able(const Node & r)
80 {
81 int sum = 0,count = 0;
82 int temp[10];
83
84 for(int i = 1;i <= 3;i ++)
85 for(int j = 1;j <= 3;j ++)
86 {
87 temp[count] = r.map[i][j];
88 count ++;
89 }
90 for(int i = 0;i < 9;i ++)
91 for(int j = i + 1;j < 9;j ++)
92 if(temp[j] < temp[i] && temp[j] && temp[i])
93 sum ++;
94 return !(sum & 1);
95 }
96
97 bool check(const int x,const int y)
98 {
99 if(x >= 1 && x <= 3 && y >= 1 && y <= 3)
100 return true;
101 return false;
102 }
103
104 void cal_hash(Node & r)
105 {
106 int sum = 0,count = 0,box;
107 int temp[10];
108
109 for(int i = 1;i <= 3;i ++)
110 for(int j = 1;j <= 3;j ++)
111 {
112 temp[count] = r.map[i][j];
113 count ++;
114 }
115 for(int i = 0;i < 9;i ++)
116 {
117 box = 0;
118 for(int j = i + 1;j < 9;j ++)
119 if(temp[j] < temp[i])
120 box ++;
121 sum += (box * HASH[i]);
122 }
123 r.hash = sum;
124 }
125
126 void search(Node const & r)
127 {
128 Node cur,next;
129
130 priority_queue<Node> que;
131 que.push(r);
132 while(!que.empty())
133 {
134 cur = que.top();
135 que.pop();
136 for(int i = 0;i < 4;i ++)
137 {
138 next = cur;
139 next.x = cur.x + UP_DATE[i][0];
140 next.y = cur.y + UP_DATE[i][1];
141 if(!check(next.x,next.y))
142 continue;
143 swap(next.map[cur.x][cur.y],next.map[next.x][next.y]);
144 cal_hash(next);
145
146 if(PATH[next.hash] == -1)
147 {
148 PATH[next.hash] = i;
149 PRE[next.hash] = cur.hash;
150 next.g ++;
151 cal_h(next);
152 que.push(next);
153 }
154 if(next.hash == GOAL)
155 {
156 show();
157 return ;
158 }
159 }
160 }
161
162 }
163
164 void cal_h(Node & r)
165 {
166 int ans = 0;
167 for(int i = 1;i <= 3;i ++)
168 for(int j = 1;j <= 3;j ++)
169 if(r.map[i][j])
170 ans += abs(i - ((r.map[i][j] - 1) / 3 + 1)) + abs(j - ((r.map[i][j] - 1) % 3 + 1));
171 r.h = ans;
172 }
173
174 void show(void)
175 {
176 string ans;
177 int hash = GOAL;
178
179 ans.clear();
180 while(PRE[hash] != -1)
181 {
182 switch(PATH[hash])
183 {
184 case 0:ans += 'l';break;
185 case 1:ans += 'r';break;
186 case 2:ans += 'u';break;
187 case 3:ans += 'd';break;
188 }
189 hash = PRE[hash];
190 }
191 for(int i = ans.size() - 1;i >= 0;i --)
192 printf("%c",ans[i]);
193 cout << endl;
194 }