題目：八數(shù)碼問題。

題意：編號為1～8的8個正方形滑塊被擺成3行3列（有一個格子留空）， 每次可以把與空格相鄰的滑塊（有公共邊才算相鄰）移到空格中，而它原來的位置就成為了新的空格。 給定初始局面和目標(biāo)局面（用0表示空格），你的任務(wù)是計算出最少的移動步數(shù)。 如果無法到達(dá)目標(biāo)局面，則輸出-1。

思路：用bfs搜索0的位置，每變換一次0，就會得到一個新局面，每個局面有8次變換。再每次變換時記錄變換步數(shù)。

參考：入門經(jīng)典-八數(shù)碼問題 - P199

代碼：

bfs:

int bfs(){    init_lookup_table();//初始化查找表    int frontt = 1,rear = 2;    while(frontt < rear){        State& s = st[frontt];        if(memcmp(goal,s,sizeof(s)) == 0) return frontt;//找到目標(biāo)        int z;        for(z=0;z<9;z++) if(!s[z]) break;//找到0位置        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;//新的0位置            if(newx >= 0 && newx < 3 && newy >= 0 && newy < 3){                State& t = st[rear];//指向隊尾，準(zhǔn)備將新序列入隊                memcpy(&t,&s,sizeof(s));//將當(dāng)前序列復(fù)制到t                t[newz] = s[z];//交換0位置                t[z] = s[newz];                dist[rear] = dist[frontt] + 1;//步數(shù)在隊首的基礎(chǔ)上加一                if(try_to_insert(rear)) rear++;//判重，不重復(fù)隊尾加一            }        }        frontt++;//出隊    }return 0;//沒有找到}int main(){    for(int i=0;i<9;i++) scanf("%d",&st[1][i]);    for(int i=0;i<9;i++) scanf("%d",&goal[i]);    int ans = bfs();    if(ans > 0) PRintf("%d/n",dist[ans]);    else printf("-1/n");    return 0;}其中init_lookup_table()和try_to_insert(rear)是判重函數(shù)：
這里提供3種方法：
（1）編碼解碼法：把0～8的全排列和0～362879的整數(shù)一一對應(yīng)起來。思路：將序列上對應(yīng)的位置的階乘 * 此位置之后小于本數(shù)的個數(shù)
比如：876543210   8! *8 + 7!*7 + ... + 0!*0
代碼：
int vis[362880],fact[9];void init_lookup_table(){    fact[0] = 1;    for(int i=1;i<9;i++) fact[i] = fact[i-1] * i;//1~8的階乘}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;//當(dāng)前序列是遞增序的第幾個    }    if(vis[code]) return 0;    return vis[code] = 1;}（2）哈希法： 只需要設(shè)計一個所謂的哈希函數(shù)h(x)，然后將任意結(jié)點x映射到某個給定范 圍 [ 0 , M-1]的整數(shù)即可
判重：建立鏈表，將哈希函數(shù)得到的位置進(jìn)行鏈表查詢，沒有找到說明不重，插入鏈表。
代碼：
const int hashsize = 1000003;int head[hashsize],next[maxstate];void init_lookup_table(){memset(head,0,sizeof(head));}int hashfun(State& s){    int v = 0;    for(int i=0;i<9;i++) v = v*10 + s[i];//將9個數(shù)字合成9位數(shù)    return v % hashsize;//確保hash函數(shù)值是不超過hash表的大小的非負(fù)整數(shù)}int try_to_insert(int s){    int h = hashfun(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;}（3）轉(zhuǎn)換數(shù)字法：直接將9個數(shù)轉(zhuǎn)換成一個9位數(shù)，然后利用set集合判重即可。
代碼：
set<int>vis;void init_lookup_table(){vis.clear();}int try_to_insert(int s){    int v = 0;    for(int i=0;i<9;i++) v = v*10 + st[s][i];    if(vis.count(v)) return 0;    vis.insert(v);    return 1;}