题目描述
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
输入输出格式
输入格式：
输入初始状态，一行九个数字，空格用0表示
输出格式：
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
输入输出样例
输入样例1：
283104765
输出样例1：
4
Solution
首先每次挪动棋子，最多把一个棋子归位，所以当有N个棋子没有归位时，最少的步数是N，
只要当前步数加上N大于最优解，就可以证明肯定不是最优解，也就不需要继续搜索了。
// luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; const int dx[5]={1,0,-1,0}; const int dy[5]={0,1,0,-1}; const int p[10]={5,1,2,3,6,9,8,7,4}; int s,flag,r[10],a[5][5],_map[5][5],dis[10][10]; bool check() { for(int i=1;i<=9;i++) if(r[i]!=p[i]) return 0; return 1; } int get() //A*剪枝 { int t=0; for(int i=1;i<=9;i++) t+=dis[r[i]][p[i]]; return t; } int jue(int a,int b) { int t=a-b; return abs(t); } int calx(int i) { return (i-1)/3+1; } int caly(int i) { return i%3==0?3:i%3; } void dfs(int depth,int x,int y) { if(depth+get()>s) return; //剪枝 if(check()) {flag=1; return;}//裸的暴搜 for(int i=0;i<4;i++) { int xx=x+dx[i],yy=y+dy[i]; if(xx<1||yy<1||xx>3||yy>3) continue; swap(a[x][y],a[xx][yy]); swap(r[a[x][y]],r[a[xx][yy]]); dfs(depth+1,xx,yy); swap(a[x][y],a[xx][yy]); swap(r[a[x][y]],r[a[xx][yy]]); } } void pre() { for(int i=1;i<=9;i++) for(int j=i+1;j<=9;j++) dis[i][j]=dis[j][i]=calx(j)-calx(i)+jue(caly(i),caly(j)); } int main() { pre(); int sx,sy; for(int i=1;i<=9;i++) { char ch=getchar(); int x=calx(i),y=caly(i); _map[x][y]=ch-'0'; r[ch-'0']=i; if(ch=='0') sx=x,sy=y; } for(s=0;;s++) { memcpy(a,_map,sizeof(_map)); dfs(0,sx,sy); if(flag) { printf("%d ",s); break; } } return 0; }