#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;
struct node{
char s[4][4];
int depth,x,y;
}q[400000];
char ans[4][4];
int k[]={1,0,-1,0,1},cx[400000],t=0;
int lal(char sb[][4])
{
int t=0;
for(int i=2;i>=0;i--)
for(int j=2;j>=0;j--)
{
t*=10;t+=sb[i][j]-'0';
}
return t;
}
int hash(node spc)
{
int t=lal(spc.s);
int t1=t%400000;
while(cx[t1]!=0)
{
if(cx[t1]==t)
return 0;
if(t1==399999)t1=0;
else t1++;
}
cx[t1]=t;
return 1;
}
int BFS()
{
int head=0,tail=1;
q[head].depth=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if(q[0].s[i][j]=='0'){q[head].x=i;q[head].y=j;break;}
while(tail!=head)
{
if(strcmp(ans[0],q[head].s[0])==0&&strcmp(ans[1],q[head].s[1])==0&&strcmp(ans[2],q[head].s[2])==0)
return q[head].depth;
for(int i=0;i<4;i++)
if(q[head].x+k[i]>=0&&q[head].x+k[i]<=2&&q[head].y+k[i+1]>=0&&q[head].y+k[i+1]<=2)
{
q[tail].depth=q[head].depth+1;
q[tail].x=q[head].x+k[i];
q[tail].y=q[head].y+k[i+1];
for(int i=0;i<3;i++)
strcpy(q[tail].s[i],q[head].s[i]);
char t=q[tail].s[q[tail].x][q[tail].y];
q[tail].s[q[tail].x][q[tail].y]='0';
q[tail].s[q[head].x][q[head].y]=t;
int m=hash(q[tail]);
if(m==1)
tail++;
tail%=400000;
}
head++;
head%=400000;
}
return -1;
}
int main()
{
ans[0][0]='1';ans[0][1]='2';ans[0][2]='3';
ans[1][0]='8';ans[1][1]='0';ans[1][2]='4';
ans[2][0]='7';ans[2][1]='6';ans[2][2]='5';
char aa[10];cin>>aa;
for(int i=0;i<10;i++)
q[0].s[i/3][i%3]=aa[i];
cout<<BFS();
return 0;
}
不就是以前的九宫重排么，小改一下就过了

#include<iostream>
#include<cstdio>
#include<string>
#include<queue>
#include<set>
using namespace std;
const int xx[4]={0,0,1,-1};
const int yy[4]={1,-1,0,0};

struct node
{
   string s;
   int step;
};
set<string>st;queue<node>q;
string aa="123804765",src;
int ans;
int bfs()
{
    node t;
    t.s=src;t.step=0;
    q.push(t);
    st.insert(src);
    while(!q.empty())
    {
        int i;
        int x,x1,y,y1;
        t=q.front();q.pop();
        if(t.s==aa)return t.step;
        for(i=0;i<=8;i++)if(t.s[i]=='0')break;
        x=i/3;y=i%3;
        for(int j=0;j<=3;j++)
        {
            x1=x+xx[j];y1=y+yy[j];
            if(x1>=0&&x1<=2&&y1>=0&&y1<=2)
            {
                node tt=t;
                int k=3*x1+y1;
                tt.s[i]=t.s[k];tt.s[k]=t.s[i];
                set<string>::iterator it;
                tt.step++;
                it=st.find(tt.s);
                if(it==st.end())
                {
                    q.push(tt);
                    st.insert(t.s);
                }
            }
        }
    }
}
int main()
{
    cin>>src;
    ans=bfs();
    cout<<ans;
    return 0;
}

测试数据 #0: Accepted, time = 15 ms, mem = 92188 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 92192 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 92192 KiB, score = 10
测试数据 #3: Accepted, time = 31 ms, mem = 92184 KiB, score = 10
测试数据 #4: Accepted, time = 156 ms, mem = 92192 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 92192 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 92192 KiB, score = 20
测试数据 #7: Accepted, time = 31 ms, mem = 92192 KiB, score = 20
Accepted, time = 263 ms, mem = 92192 KiB, score = 100
看我内存就知道了哈哈哈。。10分钟不到就打完了
http://www.cnblogs.com/Coolxxx/p/5313872.html

手抄了刘汝佳的程序
评测状态 Accepted
题目 P1360 八数码问题
递交时间 2015-10-11 10:47:40
代码语言 C++
评测机 VijosEx
消耗时间 168 ms
消耗内存 41088 KiB
评测时间 2015-10-11 10:47:41
评测结果
编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 41084 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 41080 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 41080 KiB, score = 10
测试数据 #3: Accepted, time = 31 ms, mem = 41088 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 41084 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 41084 KiB, score = 10
测试数据 #6: Accepted, time = 31 ms, mem = 41080 KiB, score = 20
测试数据 #7: Accepted, time = 31 ms, mem = 41084 KiB, score = 20
Accepted, time = 168 ms, mem = 41088 KiB, score = 100
代码
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
typedef int State[9];
const int maxstate=1000000;
State st[maxstate],goal;
int dist[maxstate];
int vis[362880];
int fact[9];

const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
void init_lookup_table()
{
fact[0]=1;
for(int i=1;i<=8;i++)fact[i]=fact[i-1]*i;
}
int try_to_insert(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+=fact[8-i]*cnt;
}
if(vis[code])return 0;
return vis[code]=1;
}
int bfs()
{
init_lookup_table();
int front=1,rear=2;
while(front<rear)
{
State& s=st[front];
if(memcmp(goal,s,sizeof(s))==0)return front;
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+dx[d];
int newy=y+dy[d];
int newz=newx*3+newy;
if(newx<0||newx>=3||newy>=3||newy<0)continue;
State& t=st[rear];
memcpy(&t,&s,sizeof(s));
t[newz]=s[z];
t[z]=s[newz];
dist[rear]=dist[front]+1;
if(try_to_insert(rear))rear++;
}
front++;
}
return 0;
}
int main()
{
int a;
scanf("%d",&a);
for(int i=8;i>=0;i--){
st[1][i]=a%10;
a/=10;
}
goal[0]=1;
goal[1]=2;
goal[2]=3;
goal[3]=8;
goal[4]=0;
goal[5]=4;
goal[6]=7;
goal[7]=6;
goal[8]=5;
int ans=bfs();
printf("%d",dist[ans]);
return 0;
}

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<string>
#include<iostream>
#include<set>
using namespace std;
const int dr[] ={1, 0, -1, 0};
const int dc[] ={0, 1, 0, -1};

int x1,y1;set<int>yu;
int a[4][4];
int s, t;

struct p{
int u[4][4], c;int dis;
int x,y;
};
int bfs()
{
queue<p>q;
p o;
memcpy(&o.u, &a, sizeof(a)); o.c = s;o.dis=0;
o.x=x1;o.y=y1;
q.push(o);
while(!q.empty())
{
p o=q.front();
q.pop();
int x=o.x,y=o.y;
if(o.c==t&&o.x==1&&o.y==1)return o.dis;
for(int i=0;i<4;i++)
{

int xo=x+dr[i];
int yo=y+dc[i];
if(xo>=0&&xo<3&&yo>=0&&yo<3){
p h;
memcpy(&h.u, &o.u, sizeof(o.u));
swap(h.u[x][y], h.u[xo][yo]);
int op=100000000;
int c=0;
for(int k=0;k<3;k++)
{
for(int j=0;j<3;j++)
{
c+=h.u[k][j]*op;op/=10;
}
}
c=c;
if(!yu.count(c))
{
h.x=xo;
h.y=yo;
h.c=c;
h.dis=o.dis+1;
yu.insert(c);
q.push(h);
}
}
}

}}
int main()
{
int c = 0;
string m;
cin>>m;

a[0][0]=m[0]-'0';
a[0][1]=m[1]-'0';
a[0][2]=m[2]-'0';
a[1][0]=m[3]-'0';
a[1][1]=m[4]-'0';
a[1][2]=m[5]-'0';
a[2][0]=m[6]-'0';
a[2][1]=m[7]-'0';
a[2][2]=m[8]-'0';
int op=100000000;
for(int i=0;i<3;i++)
{
for(int k=0;k<3;k++)
{if(a[i][k]==0){x1=i,y1=k;}
s+=op*a[i][k];
op/=10;
}
}

yu.insert(s);
t=123804765;

cout<<bfs();
return 0;
}

打表
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>

using namespace std;

struct edge{
int a,b,c;
edge(int o,int t,int ss):a(o),b(t),c(ss){}
};

inline void swap(char &a,char &b){
a^=b^=a^=b;
}

int st,l;
bool b[100000000];
int a[20000];
int ans=0;
char s[100];
queue<edge>q;

int Kangtuo(){
int n=9,ans=0;
for(int i=1;i<=n;i++){
a[i]=0;
for(int j=n;j>i;j--)if(s[i]>s[j])a[i]++;
}
int tmp=1;
ans+=a[n];
// printf("%d\n",a[n]);

for(int i=n-1;i>=1;i--){
tmp*=((n-i));
// printf("%d %d\n",a[i],tmp);
ans+=a[i]*tmp;
}
// printf("%d\n",ans+1);
return ans;
}

void work(edge it){
int tmp=it.a;
sprintf(s+1,"%09d",tmp);
// printf("%d\n",tmp);
if(it.b==l){
swap(s[1],s[2]);
sscanf(s+1,"%d",&tmp);
int x=Kangtuo();
if(!b[x]){
if(tmp==123804765){
printf("%d\n",it.c+1);
exit(0);
}
q.push(edge(tmp,l-1,it.c+1));
b[x]=true;
}
tmp=it.a;
sprintf(s+1,"%09d",tmp);
swap(s[1],s[4]);
sscanf(s+1,"%d",&tmp);
x=Kangtuo();
if(!b[x]){
if(tmp==123804765){
printf("%d\n",it.c+1);
exit(0);
}
q.push(edge(tmp,l-3,it.c+1));
b[x]=true;
}
}
else if(it.b==l-1){
swap(s[2],s[1]);
sscanf(s+1,"%d",&tmp);
int x=Kangtuo();
if(!b[x]){
if(tmp==123804765){
printf("%d\n",it.c+1);
exit(0);
}
q.push(edge(tmp,l,it.c+1));
b[x]=true;
}
tmp=it.a;
sprintf(s+1,"%09d",tmp);
swap(s[2],s[3]);
sscanf(s+1,"%d",&tmp);
x=Kangtuo();
if(!b[x]){
if(tmp==123804765){
printf("%d\n",it.c+1);
exit(0);
}
q.push(edge(tmp,l-2,it.c+1));
b[x]=true;
}
tmp=it.a;
sprintf(s+1,"%09d",tmp);
swap(s[2],s[5]);
sscanf(s+1,"%d",&tmp);
x=Kangtuo();
if(!b[x]){
if(tmp==123804765){
printf("%d\n",it.c+1);
exit(0);
}
q.push(edge(tmp,l-4,it.c+1));
b[x]=true;
}
}
else if(it.b==l-2){
swap(s[3],s[2]);
sscanf(s+1,"%d",&tmp);
int x=Kangtuo();
if(!b[x]){
if(tmp==123804765){
printf("%d\n",it.c+1);
exit(0);
}
q.push(edge(tmp,l-1,it.c+1));
b[x]=true;
}
tmp=it.a;
sprintf(s+1,"%09d",tmp);
swap(s[3],s[6]);
sscanf(s+1,"%d",&tmp);
x=Kangtuo();
if(!b[x]){
if(tmp==123804765){
printf("%d\n",it.c+1);
exit(0);
}
q.push(edge(tmp,l-5,it.c+1));
b[x]=true;
}
}
else if(it.b==l-3){
swap(s[4],s[1]);
sscanf(s+1,"%d",&tmp);
int x=Kangtuo();
if(!b[x]){
if(tmp==123804765){
printf("%d\n",it.c+1);
exit(0);
}
q.push(edge(tmp,l,it.c+1));
b[x]=true;
}
tmp=it.a;
sprintf(s+1,"%09d",tmp);
swap(s[4],s[5]);
sscanf(s+1,"%d",&tmp);
x=Kangtuo();
if(!b[x]){
if(tmp==123804765){
printf("%d\n",it.c+1);
exit(0);
}
q.push(edge(tmp,l-4,it.c+1));
b[x]=true;
}
tmp=it.a;
sprintf(s+1,"%09d",tmp);
swap(s[4],s[7]);
sscanf(s+1,"%d",&tmp);
x=Kangtuo();
if(!b[x]){
if(tmp==123804765){
printf("%d\n",it.c+1);
exit(0);
}
q.push(edge(tmp,l-6,it.c+1));
b[x]=true;
}
}
else if(it.b==l-4){
swap(s[5],s[2]);
sscanf(s+1,"%d",&tmp);
int x=Kangtuo();
if(!b[x]){
if(tmp==123804765){
printf("%d\n",it.c+1);
exit(0);
}
q.push(edge(tmp,l-1,it.c+1));
b[x]=true;
}
tmp=it.a;
sprintf(s+1,"%09d",tmp);
swap(s[5],s[4]);
sscanf(s+1,"%d",&tmp);
x=Kangtuo();
if(!b[x]){
if(tmp==123804765){
printf("%d\n",it.c+1);
exit(0);
}
q.push(edge(tmp,l-3,it.c+1));
b[x]=true;
}
tmp=it.a;
sprintf(s+1,"%09d",tmp);
swap(s[5],s[6]);
sscanf(s+1,"%d",&tmp);
x=Kangtuo();
if(!b[x]){
if(tmp==123804765){
printf("%d\n",it.c+1);
exit(0);
}
q.push(edge(tmp,l-5,it.c+1));
b[x]=true;
}
tmp=it.a;
sprintf(s+1,"%09d",tmp);
swap(s[5],s[8]);
sscanf(s+1,"%d",&tmp);
x=Kangtuo();
if(!b[x]){
if(tmp==123804765){
printf("%d\n",it.c+1);
exit(0);
}
q.push(edge(tmp,l-7,it.c+1));
b[x]=true;
}
}
else if(it.b==l-5){
swap(s[6],s[3]);
sscanf(s+1,"%d",&tmp);
int x=Kangtuo();
if(!b[x]){
if(tmp==123804765){
printf("%d\n",it.c+1);
exit(0);
}
q.push(edge(tmp,l-2,it.c+1));
b[x]=true;
}
tmp=it.a;
sprintf(s+1,"%09d",tmp);
swap(s[6],s[5]);
sscanf(s+1,"%d",&tmp);
x=Kangtuo();
if(!b[x]){
if(tmp==123804765){
printf("%d\n",it.c+1);
exit(0);
}
q.push(edge(tmp,l-4,it.c+1));
b[x]=true;
}
tmp=it.a;
sprintf(s+1,"%09d",tmp);
swap(s[6],s[9]);
sscanf(s+1,"%d",&tmp);
x=Kangtuo();
if(!b[x]){
if(tmp==123804765){
printf("%d\n",it.c+1);
exit(0);
}
q.push(edge(tmp,l-8,it.c+1));
b[x]=true;
}
}
else if(it.b==l-6){
swap(s[7],s[4]);
sscanf(s+1,"%d",&tmp);
int x=Kangtuo();
if(!b[x]){
if(tmp==123804765){
printf("%d\n",it.c+1);
exit(0);
}
q.push(edge(tmp,l-3,it.c+1));
b[x]=true;
}
tmp=it.a;
sprintf(s+1,"%09d",tmp);
swap(s[7],s[8]);
sscanf(s+1,"%d",&tmp);
x=Kangtuo();
if(!b[x]){
if(tmp==123804765){
printf("%d\n",it.c+1);
exit(0);
}
q.push(edge(tmp,l-7,it.c+1));
b[x]=true;
}
}
else if(it.b==l-7){
swap(s[8],s[5]);
sscanf(s+1,"%d",&tmp);
int x=Kangtuo();
if(!b[x]){
if(tmp==123804765){
printf("%d\n",it.c+1);
exit(0);
}
q.push(edge(tmp,l-4,it.c+1));
b[x]=true;
}
tmp=it.a;
sprintf(s+1,"%09d",tmp);
swap(s[8],s[7]);
sscanf(s+1,"%d",&tmp);
x=Kangtuo();
if(!b[x]){
if(tmp==123804765){
printf("%d\n",it.c+1);
exit(0);
}
q.push(edge(tmp,l-6,it.c+1));
b[x]=true;
}
tmp=it.a;
sprintf(s+1,"%09d",tmp);
swap(s[8],s[9]);
sscanf(s+1,"%d",&tmp);
x=Kangtuo();
if(!b[x]){
if(tmp==123804765){
printf("%d\n",it.c+1);
exit(0);
}
q.push(edge(tmp,l-8,it.c+1));
b[x]=true;
}
}
else if(it.b==l-8){
swap(s[9],s[8]);
sscanf(s+1,"%d",&tmp);
int x=Kangtuo();
if(!b[x]){
if(tmp==123804765){
printf("%d\n",it.c+1);
exit(0);
}
q.push(edge(tmp,l-7,it.c+1));
b[x]=true;
}
tmp=it.a;
sprintf(s+1,"%09d",tmp);
swap(s[9],s[6]);
sscanf(s+1,"%d",&tmp);
x=Kangtuo();
if(!b[x]){
if(tmp==123804765){
printf("%d\n",it.c+1);
exit(0);
}
q.push(edge(tmp,l-5,it.c+1));
b[x]=true;
}
}
}

int main(){
scanf("%d",&st);
if(st==123804765){
printf("0\n");
return 0;
}
sprintf(s,"%09d",st);
l=strlen(s);
int tmp=st,step=0;
while(tmp){
step++;
if(tmp%10==0)
break;
else
tmp/=10;
}
if(tmp==0)step++;
// printf("%d\n",s);
q.push(edge(st,step,0));
while(!q.empty()){
edge now=q.front();
q.pop();
work(now);
}
return 0;
}

手写队列和哈希表146ms秒杀
#include<cstring>
#include<cstdio>
using namespace std;

typedef char state[10];
const int maxn=1000000;
state st[maxn];
int dist[maxn]={0};
const state finish="123804765";
const int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};

const int hashsize=1000003;
int head[hashsize]={0},next[maxn]={0};

int hash(state s) {
int ans=0;
for (int i=0;i<9;++i) ans=ans*10+(s[i]-'0');
return ans%hashsize;
}

bool hash_insert(int s) {
int h=hash(st[s]);
int u=head[h];
while (u) {
if (!memcmp(st[u],st[s],sizeof(st[s]))) return 0;
u=next[u];
}
next[s]=head[h];
head[h]=s;
return 1;
}

int bfs() {
int front=1,rear=2;
while (front<rear) {
state &s=st[front];
if (!memcmp(finish,s,sizeof(s))) return dist[front];
int z=0;
for (z=0;z<9;++z) if (s[z]=='0') break;
int x=z/3,y=z%3;
// printf("z is %d\n",z);
for (int d=0;d<4;++d) {
int newx=x+dx[d],newy=y+dy[d];
int newz=newx*3+newy;
// printf("newx:%d newy:%d newz:%d\n",newx,newy,newz);
if (newx>=0&&newx<3&&newy>=0&&newy<3) {
state &t=st[rear];
memcpy(&t,&s,sizeof(s));
t[newz]=s[z];
t[z]=s[newz];
dist[rear]=dist[front]+1;
if (hash_insert(rear)) {
++rear;
// printf("new state:%s\n",t);
}
}
}
++front;
}
return -1;
}

int main() {
scanf("%s",st[1]);
printf("%d",bfs());
return 0;
}

c++
康托+宽搜
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;
struct node
{
int a[4][4],x,y,dep;
}list[110000];int tail,head;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
bool b[110000000];
int d[13];
int pan(node x1)
{
int a[10],k=0;

bool b[10];
for (int i=1;i<=3;i++)
for (int j=1;j<=3;j++)
a[++k]=x1.a[i][j]+1;

int kk=0;

memset(b,true,sizeof(b));
for (int i=1;i<9;i++)
{
int ans=0;
for (int j=1;j<a[i];j++)
if (b[j]) ans++;
b[a[i]]=false;

kk+=ans*d[9-i];

}
kk++;

return kk;

}
int main()
{
d[0]=1;int i,j,tt,k=0;
char ss[10];
memset(b,false,sizeof(b));
list[0].a[1][1]=1;list[0].a[1][2]=2;list[0].a[1][3]=3;
list[0].a[2][1]=8;list[0].a[2][2]=0;list[0].a[2][3]=4;
list[0].a[3][1]=7;list[0].a[3][2]=6;list[0].a[3][3]=5;
for ( i=1;i<=12;i++) d[i]=d[i-1]*i;
scanf("%s",ss+1);
for ( i=1;i<=3;i++)
for (j=1;j<=3;j++)
{
list[1].a[i][j]=ss[++k]-'0';
if (list[1].a[i][j]==0)
{
list[1].x=i;
list[1].y=j;
}

}
int an=pan(list[0]);
list[1].dep=0;
tail=head=1;
bool bk=false;

while (head<=tail)
{
for (i=0;i<=3;i++)
{
node tno;
tno=list[head];
tno.x=list[head].x+dx[i];
tno.y=list[head].y+dy[i];
if (tno.x>0 && tno.x<4 && tno.y>0 && tno.y<4)
{
tt=tno.a[tno.x][tno.y];
tno.a[tno.x][tno.y]=tno.a[list[head].x][list[head].y];
tno.a[list[head].x][list[head].y]=tt;
tno.dep=list[head].dep+1;int c=pan(tno);
if (b[c]==false)
{
list[++tail]=tno;
b[c]=true;

if (c==an)
{
printf("%d\n",tno.dep);
bk=true;break;
}
}
}
}
if (bk) break;
head++;
}
return 0;
}

http://blog.csdn.net/harlow_cheng/article/details/40451313
给个我写的题解，有3种实现方式。欢迎交流。

#include<iostream>
using namespace std;
struct node
{
int s_t[10];
long ans;
}d[500001];
bool Hash[400000]={0};
char s[10];
int B[4]={-3,-1,1,3},e_t[10]={0,1,2,3,8,0,4,7,6,5},tmp[10];
bool Flag(int a,int b)
{
if((a==1&&b==-1)||(a==1&&b==-3)||(a==2&&b==-3)||(a==3&&b==1)||(a==3&&b==-3)||(a==4&&b==-1)||(a==6&&b==1)||(a==7&&b==3)||(a==7&&b==-1)||(a==8&&b==3)||(a==9&&b==1)||(a==9&&b==3))
return 0;
return 1;
}
long Jst(int n)
{
int i;
long jst=1;
if(!n)
return 0;
for(i=1;i<=n;i++)
jst*=i;
return jst;
}
long Kto(int s[])
{
bool h[9]={0};
int co,i,k;
long hs=0;
for(i=1;i<=8;i++)
{
co=0;
for(k=s[i]-1;k>=0;k--)
{
if(!h[k])
co++;
}
h[s[i]]=1;
hs+=co*Jst(9-i);
}
return hs+1;
}
main()
{
bool flag;
int b,conut=0,i,j,t;
long head=1,hs,tail=1;
cin>>s;
for(i=0;i<9;i++)
{
d[1].s_t[i+1]=s[i]-'0';
tmp[i+1]=s[i]-'0';
}
d[1].ans=0;
Hash[Kto(tmp)]=1;
while(head<=tail)
{
for(i=1;i<=9;i++)
tmp[i]=d[head].s_t[i];
for(i=0;i<=3;i++)
{
for(j=1;j<=9;j++)
if(!tmp[j])
{
b=j;
break;
}
if(!Flag(b,B[i]))
continue;
t=tmp[b];
tmp[b]=tmp[b+B[i]];
tmp[b+B[i]]=t;
flag=0;
for(j=1;j<=9;j++)
if(tmp[j]!=e_t[j])
{
flag=1;
break;
}
if(!flag)
break;
hs=Kto(tmp);
if(!Hash[hs])
{
Hash[hs]=1;
tail++;
for(j=1;j<=9;j++)
d[tail].s_t[j]=tmp[j];
d[tail].ans=d[head].ans+1;
}
t=tmp[b];
tmp[b]=tmp[b+B[i]];
tmp[b+B[i]]=t;
}
head++;
if(!flag)
break;
}
cout<<d[head].ans+1;
}

弱弱地贴一条代码，希望对大家有所帮助。。。。。

#include<stdio.h>
#include<string.h>
const int B[4]={-3,-1,1,3};
struct node
{
int s_t[10];//当前状态
long ans;//当前步数
} d[500001]; //队列
char s[10];
bool Hash[400000]={0};//Hash
int e_t[10]={0,1,2,3,8,0,4,7,6,5},tmp[10]; //目标状态，临时变量
long Jst(int n) //求阶乘
{
if(n==0) return 0;
long jst=1;
for(int i=1;i<=n;i++)
jst*=i;
return jst;
}
long Kto(int s[])//康拓展开
{
long hs=0;int co=0;
bool h[9]={0};
for(int i=1;i<=8;i++)
{
co=0;
for(int k=s[i]-1;k>=0;k--)
{
if(!h[k]) co++; //它前面的有几个比它小？
}
h[s[i]]=true;
hs+=(co*Jst(9-i));
}
return hs+1; // 康拓展开的规则，最后一定要加1
}
bool Flag(int a,int b) //这一部分写得最丑，为了修改bug添加了这函数，
{ //哪个bug会产生错误的交换，比如tmp[3]和tmp[4]的交换
//我想重写的话，就没这么丑了
if((a==1&&b==-1) || (a==1 && b==-3)) return false;
if((a==2&&b==-3)) return false;
if((a==3&&b==1) || (a==3 && b==-3)) return false;
if((a==4&&b==-1)) return false;
if((a==6&&b==1)) return false;
if((a==7&&b==3) ||(a==7&&b==-1)) return false;
if((a==8&&b==3)) return false;
if((a==9&&b==1) || (a==9&&b==3)) return false;
return true;
}
int main()
{
int count=0;
scanf("%s",s);
for(int i=0;i<9;i++)
{
d[1].s_t[i+1]=s[i]-'0';
tmp[i+1]=s[i]-'0';
}
d[1].ans=0; //
Hash[Kto(tmp)]=true;;//
long head=1,tail=1; // 队列初始化
int b;bool flag;
while(head<=tail)
{
for(int i=1;i<=9;i++) tmp[i]=d[head].s_t[i];//取队首
for(int i=0;i<=3;i++)
{
for(int j=1;j<=9;j++)
if(tmp[j]==0){b=j;break;}// 找0的位置
if(!Flag(b,B[i])) continue; //是否越界
int t=tmp[b];tmp[b]=tmp[b+B[i]];tmp[b+B[i]]=t; //移动
flag=false;
for(int j=1;j<=9;j++) if(tmp[j]!=e_t[j]) {flag=true;break;} //判断是否到达目标状态
if(!flag) break;
long hs=Kto(tmp);
if(Hash[hs]==false) //判重
{
Hash[hs]=true;
tail++;
for(int j=1;j<=9;j++)
{
d[tail].s_t[j]=tmp[j]; //入队
}
d[tail].ans=d[head].ans+1; //是谁生成了它，便在它的步数上加1作为自己的步数
}
t=tmp[b];tmp[b]=tmp[b+B[i]];tmp[b+B[i]]=t; //换回来供他人使用
}
head++;
if(!flag) break;
}
printf("%ld\n",d[head].ans+1);
return 0;

}

400行BFS水过

#include<cstdio>
#include<cstdlib>
#include<cstring>

struct qtype{int v,t,z;};
const int mod=7654319;
bool zt[mod];
qtype q[400000];
int f,r;
int ans=0;

int fz(int x)
{
int t=1;
while (x%10!=0)
{
x/=10;
t++;
}
return 9-t;
}

int makeit(int x,int y)
{
char s[10],c;
int z,t;
bool tf=false;
z=q[x].z;
sprintf(s,"%09d",q[x].v);
if (y==1 && z-3>=0) {t=s[z];s[z]=s[z-3];s[z-3]=t;tf=true;}//与上方向交换
if (y==2 && z+3<=8) {t=s[z];s[z]=s[z+3];s[z+3]=t;tf=true;}//与下方向交换
if (y==3 && z%3!=0) {t=s[z];s[z]=s[z-1];s[z-1]=t;tf=true;}//与左方向交换
if (y==4 && (z+1)%3!=0) {t=s[z];s[z]=s[z+1];s[z+1]=t;tf=true;}//与右方向交换
if (tf==true) {sscanf(s,"%d",&t);return t;}
else return 0;
}

int main()
{
int x,t;
memset(zt,false,sizeof(zt));
scanf("%d",&x);
f=0;r=1;
q[f].v=x;q[f].t=0;q[f].z=fz(x);zt[x%mod]=true;
while (f!=r)
{
for (int i=1;i<=4;i++)
{
t=makeit(f,i);
//printf("%09d\n",t);system("pause");
if (t==0) continue;
if (t==123804765) {ans=q[f].t+1;break;}
if (zt[t%mod]==false)
{
q[r].v=t;
q[r].t=q[f].t+1;
q[r].z=fz(t);
r++;
zt[t%mod]=true;
}
}
if (ans!=0) break;
f++;
}
printf("%d",ans);
return 0;
}

感谢前面大神提供思路……8维布尔数组来记重

编译通过...

├ 测试数据 01：答案正确... (0ms, 46596KB)

├ 测试数据 02：答案正确... (805ms, 46596KB)

├ 测试数据 03：答案正确... (817ms, 46596KB)

├ 测试数据 04：答案正确... (801ms, 46596KB)

├ 测试数据 05：答案正确... (0ms, 46596KB)

├ 测试数据 06：答案正确... (0ms, 46596KB)

├ 测试数据 07：答案正确... (0ms, 46596KB)

├ 测试数据 08：答案正确... (0ms, 46596KB)

---|---|---|---|---|---|---|---|-

Accepted / 100 / 2424ms / 46596KB

view sourceprint?01 var

02 a:array[1..4] of integer=(1,-1,3,-3);

03 q:array[1..362880] of string[9]; can:array[1..4] of boolean;

04 b:array[0..100000] of longint;

05 f:array['0'..'8','0'..'8','0'..'8','0'..'8','0'..'8','0'..'8','0'..'8','0'..'8'] of boolean;

06 s,goal:string; n,ans,num,st:longint;

07 procedure init;

08 var i,j:longint;

09 begin

10 readln(s); goal:='123804765';

11 n:=length(s); st:=pos('0',s);

12 {b[1]:=1; b[2]:=2; b[3]:=3;

13 b[4]:=8; b[5]:=0; b[6]:=4;

14 b[7]:=7; b[8]:=6; b[9]:=5;}

15 end;

16 procedure swap(var a,b:char);

17 var i:char;

18 begin

19 i:=a; a:=b; b:=i;

20 end;

21 procedure bfs;

22 var head,tail,i,x:longint; p,now:string;

23 begin

24 head:=0; tail:=1; q[tail]:=s;

25 f[s[1],s[2],s[3],s[4],s[5],s[6],s[7],s[8]]:=true;

26 while head0)and(x+a[i]

单向搜索+康托hash可以秒杀

数据结构采用字符串搜索，我觉得较简单

广搜+hash秒杀

A*如何AC此题？呢？

{---|---|---|---|---|---|---|-}

总算用A*过了此题……发现自己少加了一个……然后就窘迫的90分老半天……

直接暴力就可以了

主要是会全排列hash

话说双向广搜我弄这题是最快的 pku才16ms全部通过

代码是越短越好。

Const d:array[1..4]of integer=(1,-1,3,-3);

fac:array[1..9]of longint=(1,2,6,24,120,720,5040,40320,362880);

target='123804765';

Var hash:array[0..362880]of boolean;

q:array[1..1000000]of record

s:string[9];

step:longint;

end;

now:string[9];

h,r,i,p,j:longint;

Function key(s:string[9]):longint;

var i:integer;

begin

key:=0;

for i:=1 to 8 do

inc(key,(ord(s[i])-48)*fac[i]);

end;

Procedure swap(i,j:integer);

var t:char;

begin

t:=now[i]; now[i]:=now[j]; now[j]:=t;

end;

Begin

readln(q[1].s);

fillchar(hash,sizeof(hash),false);

h:=0; r:=1;

q[1].step:=0;

hash[key(q[1].s)]:=true;

repeat

inc(h);

now:=q[h].s; p:=pos('0',now);

for i:=1 to 4 do

if (p+d[i]>=1) and (p+d[i]

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

秒杀