|
|
##[$AcWing$ $845$. 八数码](https://www.acwing.com/problem/content/847/)
|
|
|
|
|
|
### 一、题目描述
|
|
|
在一个 $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
|
|
|
```
|
|
|
|
|
|
### 二、理解与感悟
|
|
|
|
|
|
1. 为什么将二维转一维？
|
|
|
输入的是一个一维数据，就像是一个字符串。二维数组如果想对比每一次走完的棋盘是否一致，需要双重循环，比较麻烦，所以想出了一个用一维模拟二维的方法。
|
|
|
|
|
|
2. 二维怎么转一维？
|
|
|
**一维下标 = `tx * 3 + ty`**
|
|
|
|
|
|
以行号、列号下标从$0$开始为例，就是行号$\times 3 +$ 列号，比如：
|
|
|
行号为$1$(第二行)，列号为$1$(第二列)，那么$1 \times 3+1=4$，就是在一维中是第$5$个（下标从$0$开始）。
|
|
|
|
|
|
3. 一维如何还原成二维？
|
|
|
` int x = k / 3, y = k % 3;`
|
|
|
|
|
|
### 三、实现代码
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
int dx[] = {-1, 0, 1, 0};
|
|
|
int dy[] = {0, 1, 0, -1};
|
|
|
string ed = "12345678x";
|
|
|
|
|
|
unordered_map<string, int> d;
|
|
|
|
|
|
int bfs(string s) {
|
|
|
queue<string> q;
|
|
|
q.push(s);
|
|
|
d[s] = 0;
|
|
|
|
|
|
while (q.size()) {
|
|
|
auto u = q.front();
|
|
|
q.pop();
|
|
|
|
|
|
if (u == ed) return d[u];
|
|
|
int k = u.find('x');
|
|
|
int x = k / 3, y = k % 3; // 一维变二维,准备变更，判断变更后会不会出界
|
|
|
|
|
|
for (int i = 0; i < 4; i++) {
|
|
|
int tx = x + dx[i], ty = y + dy[i];
|
|
|
if (tx < 0 || tx > 2 || ty < 0 || ty > 2) continue;
|
|
|
|
|
|
string c = u; // 抄出来c
|
|
|
swap(c[k], c[tx * 3 + ty]); // 在c上进行变更，二维变一维
|
|
|
if (!d.count(c)) { // 这个状态没到达过
|
|
|
d[c] = d[u] + 1; // 记录是第几步到达
|
|
|
q.push(c);
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
return -1;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
string s;
|
|
|
char c;
|
|
|
for (int i = 1; i <= 9; i++) { // 输入的是9个字符，每两个中间有空格
|
|
|
cin >> c;
|
|
|
s += c;
|
|
|
}
|
|
|
cout << bfs(s) << endl;
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
### 四、利用康托计算全排列顺序号的思路
|
|
|
本题求最少步数，所以应当用$bfs$来做
|
|
|
|
|
|
首先定义一个能表示矩阵状态的结构体，每次把由当前状态更新的合法的新状态压入队列
|
|
|
|
|
|
如果状态为目标状态，那么返回步数，如果更新不到目标状态，返回$-1$
|
|
|
|
|
|
我们可以想到，这个$3*3$的矩阵可以表示为一个长度为$9$的字符串
|
|
|
|
|
|
但是我们知道，$bfs$需要把遍历过的状态标记，以防止死循环
|
|
|
|
|
|
**那么，如何开辟一个数组
|
|
|
使得这个数组中的元素，能够和矩阵的所有状态（长度为$9$的字符串的全排列）一一对应
|
|
|
这才是难点**
|
|
|
|
|
|
#### 全排列哈希
|
|
|
|
|
|
- 我们熟知的数一般都是常进制数，所谓常进制数就是该数的每一位都是常数进制的$k$进制数上的每一位都逢$k$进一，第$i$位的位权是$k_i$
|
|
|
- 这里要介绍一种 **变进制数**，用来表示字符串的排列状态
|
|
|
- 这种数的第$i$位逢$i$进一，第$i$位的位权是$i!$
|
|
|
用$d[i]$来表示一个变进制数第$i$位上的数字
|
|
|
|
|
|
一个$n$位变进制数的值就为$\displaystyle \sum_{i=0}^{n-1}d[i]\times i!$
|
|
|
|
|
|
这是一个最大的$9$位变进制数
|
|
|
```cpp {.line-numbers}
|
|
|
876543210
|
|
|
```
|
|
|
它对应的十进制数为
|
|
|
```cpp {.line-numbers}
|
|
|
8 × 8! + 7 × 7! + 6 × 6! + …… + 1 × 1! + 0 × 0! = 9! - 1 = 362879
|
|
|
```
|
|
|
我们可以找到一个$9$位变进制数，与一个$9$位无重复串的某种排列一一对应
|
|
|
|
|
|
用$d[i]$表示字符串中的第$i$位与其前面的字符组成的逆序对个数
|
|
|
|
|
|
字符串的一种排列对应的变进制数的值为$\displaystyle \sum_{i=0}^{n-1}d[i]\times i!$
|
|
|
|
|
|
这是字符串$123x46758$的与$d[i]$的对应关系
|
|
|
```cpp {.line-numbers}
|
|
|
i 0 1 2 3 4 5 6 7 8
|
|
|
s[i] 1 2 3 x 4 6 7 5 8
|
|
|
d[i] 0 0 0 0 1 1 1 3 1
|
|
|
```
|
|
|
它对应的变进制数的值为
|
|
|
```cpp {.line-numbers}
|
|
|
1 × 4! + 1 × 5! + 1 × 6! + 3 × 7! + 1 × 8! = 56304
|
|
|
```
|
|
|
因此可以用以下函数求字符串的一种排列对应的哈希值
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
int permutation_hash(char s[], int n){
|
|
|
int ans = 0;
|
|
|
for(int i = 0; i < n; i ++){
|
|
|
int d = 0;
|
|
|
for(int j = 0; j < i; j ++)
|
|
|
if(s[j] > s[i]) d ++;
|
|
|
ans += d * fact[i];
|
|
|
}
|
|
|
return ans;
|
|
|
}
|
|
|
```
|
|
|
$n$不能太大，通常不超过$12$，否则会溢出
|
|
|
时间复杂度为$O(n^2)$
|
|
|
|
|
|
### 五、全排列哈希 + $BFS$
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
|
|
|
struct Node {
|
|
|
string s;
|
|
|
int step;
|
|
|
int k; //'x'在第k位
|
|
|
};
|
|
|
|
|
|
int dx[] = {-1, 0, 1, 0};
|
|
|
int dy[] = {0, -1, 0, 1};
|
|
|
|
|
|
int fact[9];
|
|
|
bool st[362880];
|
|
|
|
|
|
int cantor(string s) { // 求长度为9的字符串某种排列的哈希值
|
|
|
int x = 0;
|
|
|
for (int i = 0; i < 9; i++) {
|
|
|
int smaller = 0;
|
|
|
for (int j = 0; j < i; j++)
|
|
|
if (s[j] > s[i]) smaller++; // 求s[i]与其前面的字符组成的逆序对个数
|
|
|
x += smaller * fact[i];
|
|
|
}
|
|
|
return x;
|
|
|
}
|
|
|
|
|
|
int bfs(Node u) {
|
|
|
st[cantor(u.s)] = 1;
|
|
|
queue<Node> q;
|
|
|
q.push(u);
|
|
|
|
|
|
while (q.size()) {
|
|
|
u = q.front();
|
|
|
q.pop();
|
|
|
if (u.s == "12345678x") return u.step;
|
|
|
|
|
|
int x = u.k / 3; //'x'的行数
|
|
|
int y = u.k % 3; //'x'的列数
|
|
|
Node v;
|
|
|
v.step = u.step + 1;
|
|
|
for (int i = 0; i < 4; i++) {
|
|
|
int tx = x + dx[i], ty = y + dy[i];
|
|
|
if (tx < 0 || tx > 2 || ty < 0 || ty > 2) continue;
|
|
|
// 求出'x'在字符串中的的新位置
|
|
|
v.k = tx * 3 + ty;
|
|
|
// 新串长什么样子
|
|
|
v.s = u.s; // 先抄过来
|
|
|
v.s[u.k] = u.s[v.k]; // 先用即将和'x'交换的字符覆盖'x'之前的位置
|
|
|
v.s[v.k] = 'x'; // 再给'x'的新位置赋值'x'
|
|
|
// 新串的hash值
|
|
|
int hash = cantor(v.s);
|
|
|
if (!st[hash]) {
|
|
|
st[hash] = 1;
|
|
|
q.push(v);
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
return -1;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
// 预处理fact[i] = i!
|
|
|
fact[0] = 1;
|
|
|
for (int i = 1; i < 9; i++) fact[i] = fact[i - 1] * i;
|
|
|
|
|
|
char c;
|
|
|
Node start;
|
|
|
for (int i = 0; i < 9; i++) {
|
|
|
cin >> c;
|
|
|
if (c == 'x') start.k = i;
|
|
|
start.s.push_back(c);
|
|
|
}
|
|
|
start.step = 0;
|
|
|
printf("%d", bfs(start));
|
|
|
return 0;
|
|
|
}
|
|
|
``` |
