你要把自己的思路发出来呀
by iodwad @ 2017-12-13 23:26:42
```cpp
#include<stdio.h>
int x,y,zhong[3][3]={{1,2,3},{8,0,4},{7,6,5}},a[200][3][3],max[100]={0},sum=0,x0,y0,huan[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int z(int p)//判断是否到达最终状态
{
int i,j;
for(i=0;i<=2;i++)
{
for(j=0;j<=2;j++)
{
if(a[p][i][j]!=zhong[i][j])
return 0;
}
}
return 1;
}
void ling(int l)//找出0的位置
{
int i,j;
for(i=0;i<=2;i++)
{
for(j=0;j<=2;j++)
{
if(a[l][i][j]==0)
{
x0=i;
y0=j;
return;
}
}
}
}
int pan(int f)//判断是否和之前的情况重复
{
int g,i,j,k=0;
for(g=0;g<f;g++)
{
for(i=0;i<=2;i++)
{
for(j=0;j<=2;j++)
{
if(a[g][i][j]!=a[f][i][j]) k=1;
}
}
if(k==0) return 0;
k=0;
}
return 1;
}
void play(int n)
{
if(z(n-1))
{
sum++;
max[sum]=n-1;//将所有可以走到的情况的步数保存
}
else
{
int i,j;
ling(n-1);
for(i=0;i<=2;i++)//将上一步的情况储存在将走的一步上
{
for(j=0;j<=2;j++)
{
a[n][i][j]=a[n-1][i][j];
}
}
for(i=0;i<=3;i++)
{
if(x0+huan[i][0]>=0&&x0+huan[i][0]<=2&&y0+huan[i][1]>=0&&y0+huan[i][1]<=2&&n<=20)//换0的位置
{
a[n][x0][y0]=a[n-1][x0+huan[i][0]][y0+huan[i][1]];
a[n][x0+huan[i][0]][y0+huan[i][1]]=a[n-1][x0][y0];
if(pan(n))
play(n+1);//递归，进行下一步
}
}
}
return;
}
int main()
{
int i,j,k=0,m,n=1;
char shu[10];
gets(shu);
for(i=0;i<=2;i++)
{
for(j=0;j<=2;j++)
{
a[0][i][j]=shu[k]-48;
k++;//储存初始状态
}
}
play(1);
for(m=2;m<=sum;m++)
{
if(max[m]<max[n]) n=m;
```
}//找到最短步数
printf("%d",max[n]);//打印
return 0;
}
by 测试点 @ 2017-12-14 12:27:30