有一个 3*3 的棋盘，其中有 1-9 共 9 个数字，0 表示空格,
其他的数字可以和 0 交换位置。求由初始状态到达目标状态
目标状态
如果问题无解，输出 unsolvable。
如果有解，则输出空格的移动序列。
u 表示将空格向上移，d 表示将空格向下移，l 表示左移，r 表示右移。
思路
两个unordered_map容器d和dd，分别用于保存状态到步数的映射和状态到移动方向的映射。同时还定义了一个unordered_map容器path，用于保存状态到前一个状态的映射，以便在找到解后可以回溯路径。
首先，从输入中读取初始状态start，并初始化目标状态e为固定的”123456780”。
接下来，调用bfs函数执行广度优先搜索。在搜索过程中，使用unordered_map容器d来保存已经搜索过的状态及其对应的步数。使用unordered_map容器dd来保存已经搜索过的状态及其对应的移动方向（用数字表示，0表示向下移动，1表示向上移动，2表示向左移动，3表示向右移动）。使用queue容器q来保存待搜索的状态。
在搜索过程中，首先将初始状态start入队，并将其对应的步数d[start]设为0。然后进入循环，直到队列为空。在每一次循环中，取出队列的头部状态t，并找到空格字符’0’的位置pos。如果当前状态t等于目标状态e，说明已经找到解，返回步数d[t]。
接下来，根据空格字符的位置pos，计算其所在的行x和列y。然后使用循环遍历四个移动方向，分别计算新的行坐标xx和列坐标yy。如果移动后的位置(xx, yy)在合法范围内，即xx在0到2之间，yy在0到2之间，则进行移动操作。将状态t中的空格字符’0’和位置(xx, yy)上的字符进行交换，得到新的状态new_state。如果新状态new_state在d中没有出现过（即未被访问过），则将其加入队列q中，并更新d[new_state]为d[t]+1，表示从初始状态到达新状态的步数。同时将移动方向i保存到dd[new_state]中，表示从前一个状态移动到新状态的方向。并将路径信息保存到path[new_state]中，表示新状态的前一个状态是t。
完成搜索后，如果没有找到解（d[t]仍然为0），或者找到解的步数为-1，则输出”unsolvable”。否则，调用ff函数进行路径回溯，从目标状态e开始，根据dd和path的信息逆序输出移动方向，即为从初始状态到目标状态的移动序列。
AC代码
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
| #include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<cstring>
#include<queue>
#include<unordered_map>
using namespace std;
int tt;
string start, e;
int dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,-1,1 };
unordered_map<string, int> d,dd;
unordered_map<string, string> path;
int bfs()
{
queue<string> q;
d[start] = 0;
dd[start] = -1;
q.push(start);
path[start] = "xxxx";
while (!q.empty())
{
string t = q.front();
q.pop();
int pos = t.find('0');
if (t == e)return d[t];
string str = t;
int x = pos / 3, y = pos % 3;
for (int i = 0; i <= 3; i++)
{
int xx = x + dx[i], yy = y + dy[i];
if (xx >= 0 && xx <= 2 && yy >= 0 && yy <= 2)
{
swap(t[pos], t[(xx) * 3 + yy]);
if (!d.count(t))
{
dd[t] = i;
path[t] = str;
q.push(t);
d[t] = d[str] + 1;
}
swap(t[pos], t[(xx) * 3 + yy]);
}
}
}
return -1;
}
void ff()
{
string a = "123456780";
string dis;
while (dd[a] != -1)
{
if (dd[a] == 0) dis += 'd';
if (dd[a] == 1) dis += 'u';
if (dd[a] == 2) dis += 'l';
if (dd[a] == 3) dis += 'r';
a = path[a];
}
reverse(dis.begin(), dis.end());
cout << dis;
}
int main()
{
int i = 1;
while (i <= 9)
{
char c;
cin >> c;
if (c != ' ')
{
if (c == 'x')
{
start += '0';
}
else
start += c;
i++;
}
}
e = "123456780";
int t = bfs();
if (t == -1||t == 0 )
cout << "unsolvable";
else ff();
return 0;
}
|