rockdu
题目描述
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
输入输出格式
输入格式：
输入初始状态，一行九个数字，空格用0表示
输出格式：
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
输入输出样例
输入样例#1：
283104765
输出样例#1：
4
A*的八数码（常数巨大的A*也算A*嘛），速度还是很可观的。关于A*解决八数码以及估价函数的问题可以参考这一篇博客：我是“这篇博客”
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
#include<map>
#include<string>
using namespace std;
int des[10]={1,2,3,8,0,4,7,6,5,0};
int dpos[10]={4,0,1,2,5,8,7,6,3,0};
bool vis[1000000];
int fact[]={1,1,2,6,24,120,720,5040,40320,362880};//½×³Ë±í
int ch(int * c){
int n=0;
int len=9;
for(int i=0;i<len;i++){
int cnt = 0;
for(int j=i+1;j<len;j++) if(c[i]>c[j]) cnt++;
n+= fact[len-1-i] * cnt;
}
return n;
}
struct node
{
int state[10];
int h()
{
int ret=0;
for(int i=0;i<9;i++){
int sx=i%3,sy=i/3;
int dx=dpos[state[i]]%3,dy=dpos[state[i]]/3;
ret+=abs(dx-sx)+abs(dy-sy);
}
return ret;
}
int f;
int step;
node(int rs[],int rstep)
{
for(int i=0;i<9;i++){
state[i]=rs[i]; }
step=rstep;
}
node(){ }
void judge()
{
f=step+h();
}
bool operator <(const node &a) const
{
return f>a.f;//¹ÀֵԽС Ô½ÓÅÏÈ
}
};
priority_queue<node > qn;
int fdz(int * state)
{
for(int i=0;i<9;i++)
if(state[i]==0)
return i;
}
bool tryleft(int * state,int pos)
{
if(pos%3==0) return false;
swap(state[pos],state[pos-1]);
return true;
}
bool tryright(int * state,int pos)
{
if(pos%3==2) return false;
swap(state[pos],state[pos+1]);
return true;
}
bool tryup(int * state,int pos)
{
if(pos/3==0) return false;
swap(state[pos],state[pos-3]);
return true;
}
bool trydown(int * state,int pos)
{
if(pos/3==2) return false;
swap(state[pos],state[pos+3]);
return true;
}
bool cmp(int * a,int * b){
for(int i=0;i<9;i++)
if(a[i]!=b[i]) return 0;
return 1;
}
int Astar()
{
while(!qn.empty())
{
node org;
node nstate=qn.top();
int step=nstate.step;
if(cmp(nstate.state,des))
return step;
int pos=fdz(nstate.state);
qn.pop();
org=nstate;
if(tryleft(org.state,pos))
if(!vis[ch(org.state)])
{
node newn(org.state,step+1);
newn.judge();
vis[ch(org.state)]=1;
qn.push(newn);
}
org=nstate;
if(tryright(org.state,pos))
if(!vis[ch(org.state)])
{
node newn(org.state,step+1);
newn.judge();
vis[ch(org.state)]=1;
qn.push(newn);
}
org=nstate;
if(tryup(org.state,pos))
if(!vis[ch(org.state)])
{
node newn(org.state,step+1);
newn.judge();
vis[ch(org.state)]=1;
qn.push(newn);
}
org=nstate;
if(trydown(org.state,pos))
if(!vis[ch(org.state)])
{
node newn(org.state,step+1);
newn.judge();
vis[ch(org.state)]=1;
qn.push(newn);
}
}
return -1;
}
int main()
{
int start[9];
char s[10];
gets(s);
for(int i=0;i<9;i++)
start[i]=s[i]-'0';
node st(start,0);
vis[ch(start)]=1;
st.judge();
qn.push(st);
int ans=Astar();
if(ans!=-1) printf("%d",ans);
else printf("No");
return 0;
}
没有帐号? 立即注册