【题目描述】

在一个 3×3 的网格中，1∼8 这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3 的网格中。

例如：

1 2 3
x 4 6
7 5 8

在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
4 5 6
7 8 x

例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下：

1 2 3   1 2 3   1 2 3   1 2 3
x 4 6   4 x 6   4 5 6   4 5 6
7 5 8   7 5 8   7 x 8   7 8 x

现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。

输入格式

输入占一行，将 3×3 的初始网格描绘出来。

例如，如果初始网格如下所示：

1 2 3 
x 4 6 
7 5 8 

则输入为：1 2 3 x 4 6 7 5 8

输出格式

输出占一行，包含一个整数，表示最少交换次数。

如果不存在解决方案，则输出 −1。

输入样例：

2  3  4  1  5  x  7  6  8

输出样例

19

 

字符x可以与上下左右四个方向的数字进行交换位置，可以用bfs来做，难点在于状态的存储与计算，要存储一个三维矩阵的状态比较麻烦，可以使用二维转一维的思想，直接将状态存储为一串字符串，配合哈希表的使用，更方便地存储下状态转移的步数。

 

 1 #include <iostream>
 2 #include <queue>
 3 #include <unordered_map>
 4 using namespace std;
 5 
 6 queue<string> q;
 7 unordered_map<string,int> dist;
 8 
 9 int dx[4] = {1,-1,0,0};
10 int dy[4] = {0,0,1,-1};
11 
12 int bfs(string state)
13 {
14     q.push(state);
15     dist[state] = 0;
16     
17     string end = "12345678x";
18     
19     while(q.size())
20     {
21         state = q.front();
22         q.pop();
23         if(state == end)
24             return dist[state];
25         int pos = state.find("x");
26         int a = pos / 3,b = pos % 3;
27         for(int i = 0;i <= 3;++i)
28         {
29             int x = a + dx[i],y = b + dy[i];
30             if(x < 3 && x >= 0 && y < 3 && y >= 0)
31             {
32                 string tmp = state;
33                 swap(state[pos],state[x * 3 + y]);
34                 if(!dist.count(state))
35                 {
36                     q.push(state);
37                     dist[state] = dist[tmp] + 1;
38                 }
39                 swap(state[pos],state[x * 3 + y]);
40             }
41         }
42     }
43     return -1;
44 }
45 
46 int main()
47 {
48     string start;
49     for(int i = 0;i < 9;++i)
50     {
51         char c;
52         cin >> c;
53         start += c;
54     }
55     cout << bfs(start) << endl;
56     return 0;
57 }