题目描述
在一个 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
样例
输入格式
输入占一行,将 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
康托展开写法
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
int fact[10];
int vit[362880]; //9!可以过,具体证明待补
int khash(string s)
{
int ans = 0;
for(int i = 0; i < 9; i ++)
{
int d = 0;
for(int j = 0; j < i; j ++)
if(s[j] > s[i]) d ++;
ans += d * fact[i];
}
return ans;
}
int bfs(string state){
string end = "12345678x";
queue <string> que;
que.push(state);
while (que.size()){
string g = que.front();
que.pop();
int g_hash = khash(g);
if (g == end) return vit[g_hash];
int d = vit[g_hash], k = g.find('x');
int a = k/3, b = k%3;
for (int i = 0; i < 4; ++ i){
int x = a+dx[i], y = b+dy[i];
if (x >= 0 && x < 3 && y >= 0 && y < 3){
swap(g[3*x+y], g[k]);
int t = khash(g);
if (!vit[t]) vit[t] = d+1, que.push(g);
swap(g[3*x+y], g[k]);
}
}
}
return -1;
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
string state;
for (int i = 0; i < 9; ++ i){
char op[2];
cin >> op;
state += *op;
}
fact[0] = 1;
for (int i = 1; i <= 8; ++ i) fact[i] = fact[i-1]*i;
if (state == "12345678x") cout << 0 << "\n";
else cout << bfs(state) << "\n";
return 0;
}