描述
在九宫格里放在1到8共8个数字还有一个是空格，与空格相邻的数字可以移动到空格的位置，问给定的状态最少需要几步能到达目标状态（用0表示空格）：
1 2 3
4 5 6
7 8 0
1 2 3
4 5 6
7 8 0
输入
输入一个给定的状态。
输出
输出到达目标状态的最小步数。不能到达时输出-1。
输入样例
1 2 3
4 0 6
7 5 8
4 0 6
7 5 8
输出样例
2
代码：
#include <iostream>
#include <stdio.h>
#include<queue>
#include<map> using namespace std;
int a[][];
queue<int>q;
int dir[][]={-,,,,,,,-};
int r,c;
map<int,int>visited;
map<int,int>step; int canmove(int u,int d)
{
for(int i=;i>=;i--){
for(int j=;j>=;j--){
a[i][j]=u%;
u/=;
if(a[i][j]==){
r=i;
c=j;
}
}
}
if((d==&&r==)||(d==&&c==)||(d==&&r==)||(d==&&c==))
return ;
return ;
} int moveto(int u,int d)
{
int t=;
int nr=r+dir[d][];
int nc=c+dir[d][];
a[r][c]=a[nr][nc];
a[nr][nc]=;
for(int i=;i<;i++)
for(int j=;j<=;j++)
{
t=t*+a[i][j];
}
return t;
} int bfs(int n)
{
q.push(n);
visited[n]=;
step[n]=;
while(!q.empty())
{
int u=q.front();
q.pop();
if(u==)
return step[u];
for(int i=;i<;i++)
{
if(canmove(u,i))
{
int v=moveto(u,i);
if(!visited[v])
{
visited[v]=;
step[v]=step[u]+;
q.push(v);
}
}
}
}
return -;
} int main()
{
int i,j,n=;
for(i=;i<;i++){
for(j=;j<;j++){
cin>>a[i][j];
n=n*+a[i][j];
}
}
int sum=bfs(n);
cout<<sum<<endl;
return ;
}