摘要：
BFS方法解决以抽象状态变化为基础的搜索问题。
题目
在一个 的网格中， 这 个数字和一个 x 恰好不重不漏地分布在这 的网格中。
例如：
1 2 3
x 4 6
7 5 8
在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。
我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
1 2 3
4 5 6
7 8 x
例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下：
1 2 3
x 4 6
7 5 8
to
1 2 3
4 x 6
7 5 8
to
1 2 3
4 5 6
7 x 8
to
1 2 3
4 5 6
7 8 x
现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。
输入格式
输入占一行，将 的初始网格描绘出来。
例如，如果初始网格如下所示：
1 2 3
x 4 6
7 5 8
则输入为：1 2 3 x 4 6 7 5 8
输出格式
输出占一行，包含一个整数，表示最少交换次数。
如果不存在解决方案，则输出 。
输入样例：
2 3 4 1 5 x 7 6 8
输出样例
19
代码
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
|
#include <bits/stdc++.h>
using namespace std;
unordered_map<string, int> d;
queue<string> q;
int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};
int res = -1;
void bfs(string graph)
{
q.push(graph);
d[graph] = 0;
string final_graph = "12345678x";
for (; q.size(); )
{
string cur = q.front();
q.pop();
int distance = d[cur];
if (cur == final_graph)
{
res = distance;
return;
}
int pos = cur.find('x');
int r = pos / 3, c = pos % 3;
for (int i = 0; i < 4; ++ i)
{
int ner = r + dr[i], nec = c + dc[i];
if (ner >= 0 && ner < 3 && nec >= 0 && nec < 3)
{
int ne_pos = ner * 3 + nec;
swap(cur[pos], cur[ne_pos]);
if (d[cur] == 0)
{
q.push(cur);
d[cur] = distance + 1;
}
swap(cur[pos], cur[ne_pos]);
}
}
}
}
int main()
{
string start;
for (char c; cin >> c; start += c);
bfs(start);
cout << res << endl;
}
|
理解
仔细阅读题目可以看出这道题涉及到方格状态的演变，状态不断叠加直到产生正确的结果。这和在棋盘上从某点到某点的搜索过程类似。
在使用BFS搜索棋盘从某点到某点的路径时，点的一次移动可视为状态的一次变化。在此处BFS的思想体现在点向四个方向移动进行搜索尝试直到找到路径。
而本题可将从当前地图状态到 与周围的某个数字发生一次位置交换后的状态视为状态的一次变化。注意这里和上述路径搜索不同的地方在于状态的变化。此处为地图的当前布局到移动数字后的一次布局，而上述路径搜索则很直观地体现在点的移动。
我们使用BFS思想不断尝试 周围的点与 进行交换，直到找到目标状态。
在使用BFS前，我们思考如何将棋盘的一个布局视为BFS的一个虚拟节点。以及如何存放状态变化过程中进行的次数。
我们可将矩阵按行拆分拼成一行，转化为字符串，将某个字符串视为一个节点，每一次状态变化后，将字符串放入队列。
我们可维护一个哈希表，key为矩阵字符串，value为状态转移过程中进行的次数。
本题有个小技巧： 的矩阵中某点 的横纵坐标 可以看成将矩阵按行排成一行后， 的下标 进行如下处理：
1
2
| int r = i / m;
int c = i % m;
|
相反：