Description
如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。
我们把第一个图的局面记为：12345678.
把第二个图的局面记为：123.46758
显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。
我们把第一个图的局面记为：12345678.
把第二个图的局面记为：123.46758
显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。
Input
输入第一行包含九宫的初态，第二行包含九宫的终态。
Output
输出最少的步数，如果不存在方案，则输出-1。
Sample Input
样例输入1
12345678.
123.46758 样例输入2
13524678.
46758123.
Sample Output
样例输出1
3 样例输出2
22
Source
蓝桥杯
分析：暴力bfs会超时
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define INF 99999999
#define me(a,x) memset(a,x,sizeof(a))
int mon1[]= {,,,,,,,,,,,,};
int mon2[]= {,,,,,,,,,,,,};
int dir[][]= {{,},{,-},{,},{-,}};
int fac[] = {, , , , , , , , , };//i的阶乘 LL getval()
{
LL ret();
char c;
while((c=getchar())==' '||c=='\n'||c=='\r');
ret=c-'';
while((c=getchar())!=' '&&c!='\n'&&c!='\r')
ret=ret*+c-'';
return ret;
}
void out(int a)
{
if(a>)
out(a/);
putchar(a%+'');
}
int kt(int a[],int n)//康托展开
{
int ans=;
for(int i=;i<=n;i++)
{
int c=;
for(int j=i+;j<=n;j++)
{
if(a[j]<a[i])
c++;
}
ans+=(c*fac[n-i]);
}
return ans+;
} char str1[],str2[];
int a[][],b[][];
int sx,sy;
int t[];
int h;
int w;
bool vis[]; struct node
{
int x,y,step;//x,y代表空格位置
int c[][];//九宫格数组
node(int xx,int yy,int ss,int cc[][])//初始化
{
x=xx;
y=yy;
step=ss;
for(int i=; i<=; i++)
for(int j=; j<=; j++)
c[i][j]=cc[i][j];
}
int getkt()//得到结点数组的康托展开值
{
h=;
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
t[h++]=c[i][j];
}
}
return kt(t,);
}
}; void init()//初始化
{
int cnt=;
for(int i=; i<=; i++)//得到原始九宫格
{
for(int j=; j<=; j++)
{
if(str1[cnt]=='.')
a[i][j]=,sx=i,sy=j;
else
a[i][j]=str1[cnt]-'';
cnt++;
}
}
cnt=;
for(int i=; i<=; i++)//得到目标九宫格
{
for(int j=; j<=; j++)
{
if(str2[cnt]=='.')
b[i][j]=;
else
b[i][j]=str2[cnt]-'';
cnt++;
}
}
me(vis,false);//九宫格状态数组
h=;
for(int i=;i<=;i++)//得到目标九宫格的康托展开值
{
for(int j=;j<=;j++)
{
t[h++]=b[i][j];
}
}
w=kt(t,);
}
int check(int x,int y)//边界约束
{
if(x<=&&x>=&&y<=&&y>=)
return ;
return ;
}
int bfs(int x,int y,int a[][])
{
queue<node> q; q.push(node(x,y,,a));
vis[node(x,y,,a).getkt()]=; while(!q.empty())
{
int x=q.front().x;
int y=q.front().y;
int step=q.front().step;
int c[][];
for(int i=; i<=; i++)
for(int j=; j<=; j++)
c[i][j]=q.front().c[i][j];
q.pop(); for(int i=; i<; i++)
{
int xx=x+dir[i][];
int yy=y+dir[i][];
int ss=step+; int cc[][];
if(check(xx,yy)==)//越界
continue; for(int i=; i<=; i++)
for(int j=; j<=; j++)
cc[i][j]=c[i][j];
cc[x][y]=cc[xx][yy];//移动
cc[xx][yy]=; if(vis[node(xx,yy,ss,cc).getkt()]==)//判断该状态的九宫格有没有搜索过
{
if(node(xx,yy,ss,cc).getkt()==w)//搜索到了目标
{
return ss;//返回步数
}
int temp=node(xx,yy,ss,cc).getkt(); vis[temp]=;//标记该状态的九宫格已经搜索过
q.push(node(xx,yy,ss,cc));
} }
}
return -;
}
int main()
{
while(~scanf("%s",str1))
{
scanf("%s",str2);
init(); int ans=bfs(sx,sy,a);
printf("%d\n",ans);
}
}