#include<iostream>//样例210486753，答案16
#include<cstdio>
#include<cstring>
using namespace std;
int vis[400000],f[9];
int st[1000000][10],goal[10]= {1,2,3,8,0,4,7,6,5};
int step[1000000];
int bx[4]= {-1,1,0,0};
int by[4]= {0,0,1,-1};
void gdjfhfjha() {
f[0]=1;
for(int i=1; i<9; i++) {
f[i]=f[i-1]*i;
}
}
int check(int s) {
int code=0;
for(int i=0;i<9;i++)
{
int cnt=0;
for(int j=i+1;j<9;j++)if(st[s][j]<st[s][i])cnt++;
code+=f[8-i]*cnt;
}//先把s行的状态转为code
if(vis[code])return 1;
return vis[code]=0;
}
int bfs() {
int t=1;
int w=2;
while(t<w) {
int s[10];
int ok=1;
for(int i=0; i<9; i++) {
s[i]=st[t][i];
if(s[i]!=goal[i])
{
ok=0;
}
}
if(ok) {
cout<<step[t];
return 0;
}
int z;
for(z=0; z<9; ++z)
if(!s[z])
break;
int x=z/3,y=z%3;
for(int d=0; d<4; d++) {
int newx=x+bx[d];
int newy=y+by[d];
int newz=newx*3+newy;
if(newx>=0&&newx<3&&newy>=0&&newy<3) {
int tt[10];
for(int i=0; i<9; i++) {
tt[i]=s[i];
}
int tmp=tt[newz];
tt[newz]=0;
tt[z]=tmp;
for(int i=0; i<9; i++) {
st[w][i]=tt[i];
}
step[w]=step[t]+1;
if(!check(w))w++;
}
}
t++;
}
return 0;
}
int main() {
char ch;
for(int i=0; i<9; i++) {
cin>>ch;
st[1][i]=ch-'0';
}
bfs();
return 0;
}
题目描述\ Yours和zero在研究A启发式算法.拿到一道经典的A问题,但是他们不会做,请你帮他们. 在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
输入\ 输入初试状态，一行九个数字，空格用0表示
输出\ 只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
样例输入\ 283104765
样例输出\ 4
你好，我是有问必答小助手，非常抱歉，本次您提出的有问必答问题，技术专家团超时未为您做出解答
本次提问扣除的有问必答次数，将会以问答VIP体验卡（1次有问必答机会、商城购买实体图书享受95折优惠）的形式为您补发到账户。
因为有问必答VIP体验卡有效期仅有1天，您在需要使用的时候【私信】联系我，我会为您补发。