3243 - 八数码
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
Input
输入初试状态，一行九个数字，空格用0表示
Output
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
Examples
Input
283104765
Output
4
Solution C++
/* Name: 八数码 Date: 14/10/14 20:21 Description: IDA* */ #include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> using namespace std; int now[10]; char c; int to[10]={0,1,2,3,8,0,4,7,6,5}; int pos0=0,deep=0,h; int f(){ int fnow[10]; int fto[10]; int tot=0; for(int i=1;i<=9;++i){ fnow[now[i]]=i-1; fto[to[i]]=i-1; } for(int i=1;i<9;++i){ tot+=abs(fnow[i]/3-fto[i]/3)+abs(fnow[i]%3-fto[i]%3); } return tot; } void dfs(int ans,int pos){ h=f(); if(h+ans>deep) return; if(ans==deep) { cout<<ans<<endl; exit(0); } if(pos!=1&&pos!=4&&pos!=7){ swap(now[pos],now[pos-1]); dfs(ans+1,pos-1); swap(now[pos],now[pos-1]); } if(pos!=3&&pos!=6&&pos!=9){ swap(now[pos],now[pos+1]); dfs(ans+1,pos+1); swap(now[pos],now[pos+1]); } if(pos>3){ swap(now[pos],now[pos-3]); dfs(ans+1,pos-3); swap(now[pos],now[pos-3]); } if(pos<7){ swap(now[pos],now[pos+3]); dfs(ans+1,pos+3); swap(now[pos],now[pos+3]); } } int main(){ /*freopen("1.in","r",stdin); for(int i=1;i<=9;++i){ cin>>now[i]; if(now[i]==0) pos0=i; }*/ for(int i=1;i<=9;++i){ cin>>c; now[i]=(int)c-48; if(now[i]==0) pos0=i; } while(1){ dfs(0,pos0); ++deep; } }