题目描述
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
输入输出格式
输入格式：
输入初试状态，一行九个数字，空格用0表示
输出格式：
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
输入输出样例
输入样例#1：
283104765
输出样例#1：
4
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std; //目标态
int fin[][]={{,},{,},{,},{,},{,},{,},{,},{,},{,}}; struct State{
int a[][];
}; int lim=,ok; //计算f(n)函数
int H(const State &st){
int ret=;
for(int i=;i<;i++)
for(int j=;j<;j++){
int t=st.a[i][j];
if(t) ret+=abs(fin[t][]-i)+abs(fin[t][]-j);
}
return ret;
} void dfs(State st,int g){
int h=H(st);
if(ok||g+h>lim)
return;
if(!h){
ok=;
return;
}
int x,y;
for(int i=;i<;i++)
for(int j=;j<;j++)
if(!st.a[i][j]){
x=i,y=j;
break;
}
if(x>){
swap(st.a[x][y],st.a[x-][y]);
dfs(st,g+);
swap(st.a[x][y],st.a[x-][y]);
}
if(x<){
swap(st.a[x][y],st.a[x+][y]);
dfs(st,g+);
swap(st.a[x][y],st.a[x+][y]);
}
if(y>){
swap(st.a[x][y],st.a[x][y-]);
dfs(st,g+);
swap(st.a[x][y],st.a[x][y-]);
}
if(y<){
swap(st.a[x][y],st.a[x][y+]);
dfs(st,g+);
swap(st.a[x][y],st.a[x][y+]);
}
} int main(){
State st;
char ch[];
scanf("%s",ch);
for(int i=;i<;i++)
for(int j=;j<;j++)
st.a[i][j]=ch[i*+j]-'';
while(++lim){
dfs(st,);
if(ok) break;
}
printf("%d\n",lim);
return ;
}
在写盲目bfs 1590ms 后很久才用的IDA*解法
感谢will7101在luogu上题解给本蒟蒻此题IDA*稍短代码的启蒙
终于学会了计算h(n) QwQ
总是在梦里我看到你无助的双眼 我的心又一次被唤醒