【题解】HDU-1043 Eight

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
2
3
4
 1  2  3  4
5 6 7 8
9 10 11 12
13 14 15 x

where 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
2
3
4
5
 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->

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.

样例输入

1
2  3  4  1  5  x  7  6  8

样例输出

1
ullddrurdllurdruldr

提示

思路

考虑多次bfs会TLE,而目标状态是确定的,且由此bfs出的所有状态也是有限的(9!),所以这题不是bfs直接搜出来的,而是bfs打表。 暂时没用康拓展开,不过最好去看看,同时感兴趣的圣雄甘地可以了解一下八数码八境界…

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1e2+5;

int n = 9;

int dx[] = { 1, -1, 0, 0};
int dy[] = { 0, 0, 1, -1};
char dir[] = "udlr";

struct P {
string s, p;
int x;
};

map<int, string> mp;

void bfs() {
P sp;
sp.s = "123456789";
sp.p = "";
sp.x = n-1;

queue<P> q;
q.push(sp);
mp[123456789] = "";

while(!q.empty()) {
P tp = q.front();
q.pop();

P np;
for(int i=0; i<4; i++) {
int x = tp.x/3+dx[i];
int y = tp.x%3+dy[i];
if(x<0 || x>=3 || y<0 || y>=3) {
continue;
}
np = tp;
np.x = x*3+y;
swap(np.s[np.x], np.s[tp.x]);

int d=0;
for(int i=0; i<n; i++) {
d = d*10+np.s[i]-'0';
}

if(mp.find(d)==mp.end()) {
np.p += i+'0';
q.push(np);
mp[d] = np.p;
};
}
}
}

int main(void) {
bfs();

char c;
while(scanf(" %c", &c)==1) {
int d;
if(c=='x') {
d = 9;
} else {
d = c-'0';
}
for(int i=1; i<n; i++) {
scanf(" %c", &c);
if(c=='x') {
d = d*10+9;
} else {
d = d*10+c-'0';
}
}
if(mp.find(d)==mp.end()) {
printf("unsolvable\n");
} else {
string p = mp[d];
for(int i=p.length()-1; i>=0; i--)
printf("%c", dir[p[i]-'0']);
printf("\n");
}
}

return 0;
}