Eight (HDU - 1043)
题面
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 1 2 3 4 2 5 6 7 8 3 9 10 11 12 413 14 15 xwhere the only legal operation is to exchange ‘x’ with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle:
1 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 2 5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8 3 9 x 10 12 9 10 x 12 9 10 11 12 9 10 11 12 413 14 11 15 13 14 11 15 13 14 x 15 13 14 15 x 5 r-> d-> r->The letters in the previous row indicate which neighbor of the ‘x’ tile is swapped with the ‘x’ tile at each step; legal values are ‘r’,’l’,‘u’ and ’d’, for right, left, up, and down, respectively.
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.
输入
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
输出
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.
样例输入
12 3 4 1 5 x 7 6 8
样例输出
1ullddrurdllurdruldr
提示
无
思路
考虑多次bfs会TLE，而目标状态是确定的，且由此bfs出的所有状态也是有限的(9!)，所以这题不是bfs直接搜出来的，而是bfs打表。 暂时没用康拓展开，不过最好去看看，同时感兴趣的圣雄甘地可以了解一下八数码八境界…
代码
1using namespace std;
2typedef long long ll;
3const int inf = 0x3f3f3f3f;
4const int N = 1e2+5;
5
6int n = 9;
7
8int dx[] = { 1, -1, 0, 0};
9int dy[] = { 0, 0, 1, -1};
10char dir[] = "udlr";
11
12struct P {
13 string s, p;
14 int x;
15};
16
17map<int, string> mp;
18
19void bfs() {
20 P sp;
21 sp.s = "123456789";
22 sp.p = "";
23 sp.x = n-1;
24
25 queue<P> q;
26 q.push(sp);
27 mp[123456789] = "";
28
29 while(!q.empty()) {
30 P tp = q.front();
31 q.pop();
32
33 P np;
34 for(int i=0; i<4; i++) {
35 int x = tp.x/3+dx[i];
36 int y = tp.x%3+dy[i];
37 if(x<0 || x>=3 || y<0 || y>=3) {
38 continue;
39 }
40 np = tp;
41 np.x = x*3+y;
42 swap(np.s[np.x], np.s[tp.x]);
43
44 int d=0;
45 for(int i=0; i<n; i++) {
46 d = d*10+np.s[i]-'0';
47 }
48
49 if(mp.find(d)==mp.end()) {
50 np.p += i+'0';
51 q.push(np);
52 mp[d] = np.p;
53 };
54 }
55 }
56}
57
58int main(void) {
59 bfs();
60
61 char c;
62 while(scanf(" %c", &c)==1) {
63 int d;
64 if(c=='x') {
65 d = 9;
66 } else {
67 d = c-'0';
68 }
69 for(int i=1; i<n; i++) {
70 scanf(" %c", &c);
71 if(c=='x') {
72 d = d*10+9;
73 } else {
74 d = d*10+c-'0';
75 }
76 }
77 if(mp.find(d)==mp.end()) {
78 printf("unsolvable\n");
79 } else {
80 string p = mp[d];
81 for(int i=p.length()-1; i>=0; i--)
82 printf("%c", dir[p[i]-'0']);
83 printf("\n");
84 }
85 }
86
87 return 0;
88}