特别声明:紫书上抄来的代码,详见P198 

题目描述

在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入输出格式

输入格式：

输入初试状态，一行九个数字，空格用0表示

输出格式：

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)

输入输出样例

283104765

4

判重一 //set

代码

 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<set>//测试  5 #include<algorithm> 6 using namespace std; 7 typedef int state[9]; 8  9 state st[1000005],goal={1,2,3,8,0,4,7,6,5};10 int dis[1000005],dx[]={-1,1,0,0},dy[]={0,0,-1,1};11 12 set<int> vis;13 void init_lookup_table(){vis.clear();}14 int try_to_insert(int s){15     int v=0;16     for(int i=0;i<9;i++)v=v*10+st[s][i];17     if(vis.count(v)) return 0;18     vis.insert(v);19     return 1;20 }21 22 int bfs(){23     init_lookup_table();24     int front=1,rear=2;25     while(front<rear){26         state& s=st[front];27         if(memcmp(goal,s,sizeof(s))==0)return front;28         29         int z;30         for(z=0;z<9;z++) if(!s[z]) break;31         int x=z/3,y=z%3;32         for(int d=0;d<4;d++){33             int newx=x+dx[d];34             int newy=y+dy[d];35             int newz=newx*3+newy;36             if(newx>=0&&newx<3&&newy>=0&&newy<3){37                 state& t=st[rear];38                 memcpy(&t,&s,sizeof(s));//Copy39                 t[newz]=s[z];40                 t[z]=s[newz];41                 dis[rear]=dis[front]+1;42                 if(try_to_insert(rear)) rear++;43             }44         }45         front++;46     }47     return 0;48 }49 50 int main(){51 //    freopen("01.in","r",stdin);52     string s;cin>>s;53     for(int i=0;i<=9;i++)st[1][i]=s[i]-‘0‘;54     55     int ans=bfs();56     if(ans>0) printf("%d\n",dis[ans]);57     else printf("-1\n");58     return 0;59 }

紫书上说stl很慢,但是......

膜拜洛谷测评机

 

不过这是一个好方法吧.比如状态很多但很分散就可以类比set

判重二 //hash

代码 

#include<iostream>#include<cstring>#include<cstdio>#include<set>//测试 #include<algorithm>using namespace std;typedef int state[9];state st[1000005],goal={1,2,3,8,0,4,7,6,5};int dis[1000005],dx[]={-1,1,0,0},dy[]={0,0,-1,1};const int hashsize=1000003;int head[hashsize],next[hashsize];void init_lookup_table(){memset(head,0,sizeof(head));}int hash(state& s){    int v=0;    for(int i=0;i<9;i++) v=v*10+s[i];    return v%1000003;}int try_to_insert(int s){    int h=hash(st[s]);    int u=head[h];    while(u){        if(memcmp(st[u],st[s],sizeof(st[s]))==0 )return 0;        u=next[u];    }    next[s]=head[h];    head[h]=s;    return 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>=0&&newy<3){                state& t=st[rear];                memcpy(&t,&s,sizeof(s));//Copy                t[newz]=s[z];                t[z]=s[newz];                dis[rear]=dis[front]+1;                if(try_to_insert(rear)) rear++;            }        }        front++;    }    return 0;}int main(){//    freopen("01.in","r",stdin);    string s;cin>>s;    for(int i=0;i<=9;i++)st[1][i]=s[i]-‘0‘;        int ans=bfs();    if(ans>0) printf("%d\n",dis[ans]);    else printf("-1\n");    return 0;}

震惊!!!

 判重三 //编码(只适用于码数很小的情况下,比如30!就不行)

代码

 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<set>//测试  5 #include<algorithm> 6 using namespace std; 7 typedef int state[9]; 8  9 state st[1000005],goal={1,2,3,8,0,4,7,6,5};10 int dis[1000005],dx[]={-1,1,0,0},dy[]={0,0,-1,1};11 12 int vis[362880],fact[9];13 void init_lookup_table(){14     fact[0]=1;15     for(int i=1;i<9;i++) fact[i]=fact[i-1]*i;16 }17 int try_to_insert(int s){18     int code=0;//把st[s]映射到整数code19     for(int i=0;i<9;i++){20         int cnt=0;21         for(int j=i+1;j<9;j++)if(st[s][j]<st[s][i]) cnt++;22         code+=fact[8-i]*cnt;23     }24     if(vis[code])return 0;25     return vis[code]=1;26 }27 28 int bfs(){29     init_lookup_table();30     int front=1,rear=2;31     while(front<rear){32         state& s=st[front];33         if(memcmp(goal,s,sizeof(s))==0)return front;34         35         int z;36         for(z=0;z<9;z++) if(!s[z]) break;37         int x=z/3,y=z%3;38         for(int d=0;d<4;d++){39             int newx=x+dx[d];40             int newy=y+dy[d];41             int newz=newx*3+newy;42             if(newx>=0&&newx<3&&newy>=0&&newy<3){43                 state& t=st[rear];44                 memcpy(&t,&s,sizeof(s));//Copy45                 t[newz]=s[z];46                 t[z]=s[newz];47                 dis[rear]=dis[front]+1;48                 if(try_to_insert(rear)) rear++;49             }50         }51         front++;52     }53     return 0;54 }55 56 int main(){57 //    freopen("01.in","r",stdin);58     string s;cin>>s;59     for(int i=0;i<=9;i++)st[1][i]=s[i]-‘0‘;60     61     int ans=bfs();62     if(ans>0) printf("%d\n",dis[ans]);63     else printf("-1\n");64     return 0;65 }

总结起来就是:效率 hash>编码>set

另外这里有一个详细的转载：http://blog.csdn.net/ouxijv/article/details/7203027

洛谷 P1379 八数码难题 Label:判重&&bfs