问题描述
如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。
我们把第一个图的局面记为：12345678.
把第二个图的局面记为：123.46758
显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。
我们把第一个图的局面记为：12345678.
把第二个图的局面记为：123.46758
显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。
输入格式
输入第一行包含九宫的初态，第二行包含九宫的终态。
输出格式
输出最少的步数，如果不存在方案，则输出-1。
样例输入
12345678.
123.46758
123.46758
样例输出
3
样例输入
13524678.
46758123.
46758123.
样例输出
22
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
typedef struct nn
{
int loc,c[10],step;
}Node;
int dir[4][2]={1,0,-1,0,0,1,0,-1};
int jc[9]={1,1,2,6,24,120,720,5040,40320};
int cantuo(int c[])
{
int sum=0,k;
for(int i=0;i<9;i++)
{
k=0;
for(int j=i+1;j<9;j++)
if(c[j]<c[i]) k++;
sum+=k*jc[8-i];
}
return sum;
}
int find(int c[],int num1,int num2)
{
if(num1==num2) return 0;
queue<Node>q;
Node now,next;
int x,y,num,tm,f[400000];
memset(f,0,sizeof(f));
for(int i=0;i<9;i++)
{
if(c[i]==9)
now.loc=i;
now.c[i]=c[i];
}
now.step=0;
f[num1]=1;
q.push(now);
while(!q.empty())
{
now=q.front(); q.pop();
for(int e=0;e<4;e++)
{
x=now.loc/3+dir[e][0];
y=now.loc%3+dir[e][1];
if(x>=0&&x<3&&y>=0&&y<3)
{
next=now;
next.step++;
next.loc=x*3+y;
tm=next.c[now.loc];
next.c[now.loc]=next.c[x*3+y];
next.c[x*3+y]=tm;
num=cantuo(next.c);
if(num==num2) return next.step;
if(!f[num])
{
f[num]=1;
q.push(next);
}
}
}
}
return -1;
}
int main()
{
int c[10],tc[10],num1,num2,step;
char ch[10],tch[10];
scanf("%s%s",ch,tch);
for(int i=0;i<9;i++)
{
if(ch[i]>='1'&&ch[i]<='8')
c[i]=ch[i]-'0';
else c[i]=9;
if(tch[i]>='1'&&tch[i]<='8')
tc[i]=tch[i]-'0';
else tc[i]=9;
}
num1=cantuo(c);
num2=cantuo(tc);
printf("%d\n",find(c,num1,num2));
}