问题描述
如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。
我们把第一个图的局面记为：12345678.
把第二个图的局面记为：123.46758
显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。
我们把第一个图的局面记为：12345678.
把第二个图的局面记为：123.46758
显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。
输入格式
输入第一行包含九宫的初态，第二行包含九宫的终态。
输出格式
输出最少的步数，如果不存在方案，则输出-1。
样例输入
12345678.
123.46758
123.46758
样例输出
3
样例输入
13524678.
46758123.
46758123.
样例输出
22
==========================分割线==================================
这个题刚开始直接用bfs去做，但是开的标记数组的维数会非常高，后来才在网上看到用康拓展开，能用到康拓展开是因为这可以看成是一个序列，所以可以用康拓展开求出他在全排列中的次序，这样标记数组就可以开一维的了，这道题的广搜和三个水杯那个题差不多
代码如下：
#include<iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
typedef long long LL;
struct Node{
int cur[];
LL step;
};
Node s, e;
const int N = 1e6;
const int Next[][] = {{, }, {, }, {-, }, {, -}};//搜索的四个方向
bool vis[N * ];//标记数组
int fac[] = {, , , , , , , , , };//前几个数的阶乘
LL cantor(int s[])//康拓展开
{
LL ans = ;
int n = ;
for (int i = ; i < n - ; i++)
{
int tmp = ;
for (int j = i + ; j < n; j++)
if (s[j] < s[i])
tmp++;
ans += fac[n - i - ] * tmp;
}
return ans;
}
void cantor_reverse(int index, int a[])//康拓展开逆， 在本道题中未使用
{
index--;
int n = ;
bool visit[];
memset(visit, false, sizeof(visit));
for (int i = ; i < n; i++)
{
int tmp = index / fac[n - i - ];
for (int j = ; j <= tmp; j++)
if (visit[j])
tmp++;
a[i] = tmp + ;
visit[tmp] = true;
index %= fac[n - i - ];
}
}
bool ischecked(int row, int col)//检查是否满足移动的条件
{
return (row > && col > && row < && col < );
}
bool matched(Node node)//看是否达到给定的状态
{
for (int i = ; i < ; i++)
if (node.cur[i] != e.cur[i])
return false;
return true;
}
LL bfs()
{
memset(vis, false, sizeof(vis));
queue<Node> Q;
s.step = ;
Q.push(s);
Node p, q;
int start_num = cantor(s.cur);
vis[start_num] = true;//标记第一个元素
while (!Q.empty())
{
p = Q.front();
Q.pop();
int pos;
for (pos = ; pos < ; pos++)
if (p.cur[pos] == )//将"."当成9来计算
break;
int row, col, new_row, new_col;
row = pos / + ;
col = pos % + ;
for (int i = ; i < ; i++)
{
new_row = row + Next[i][];
new_col = col + Next[i][];
if (ischecked(new_row, new_col))//判断是否满足可移动的条件
{
q = p;
q.step = p.step + ;
//下面三步是交换这两个数(也就是移动到空位去)
int t = q.cur[(row - ) * + col - ];
q.cur[(row - ) * + col - ] = q.cur[(new_row - ) * + new_col - ];
q.cur[(new_row - ) * + new_col - ] = t;
if (matched(q))//如果找到之后直接返回
{
return q.step;
}
int num = cantor(q.cur);
if (!vis[num])
{
vis[num] = true;
Q.push(q);
}
}
}
}
return -;//找不到就返回-1
}
int main()
{
char sta[], en[];
scanf("%s %s", sta, en);
for (int i = ; i < ; i++)
if (sta[i] != '.')
s.cur[i] = sta[i] - '';
else
s.cur[i] = ;//将'.'看成9
for (int i = ; i < ; i++)
if (en[i] != '.')
e.cur[i] = en[i] - '';
else
e.cur[i] = ;
LL tmp = bfs();
printf("%lld\n", tmp); return ;
}