八数码问题 【隐式图bfs】

题目：八数码问题。

题意：编号为1～8的8个正方形滑块被摆成3行3列（有一个格子留空）， 每次可以把与空格相邻的滑块（有公共边才算相邻）移到空格中，而它原来的位置就成为了新的空格。 给定初始局面和目标局面（用0表示空格），你的任务是计算出最少的移动步数。 如果无法到达目标局面，则输出-1。

思路：用bfs搜索0的位置，每变换一次0，就会得到一个新局面，每个局面有8次变换。再每次变换时记录变换步数。

参考：入门经典-八数码问题 - 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;//找到目标        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];//指向队尾，准备将新序列入队                memcpy(&t,&s,sizeof(s));//将当前序列复制到t                t[newz] = s[z];//交换0位置                t[z] = s[newz];                dist[rear] = dist[frontt] + 1;//步数在队首的基础上加一                if(try_to_insert(rear)) rear++;//判重，不重复队尾加一            }        }        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)是判重函数：
这里提供3种方法：
（1）编码解码法：把0～8的全排列和0～362879的整数一一对应起来。思路：将序列上对应的位置的阶乘 * 此位置之后小于本数的个数
比如：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;//当前序列是递增序的第几个    }    if(vis[code]) return 0;    return vis[code] = 1;}（2）哈希法： 只需要设计一个所谓的哈希函数h(x)，然后将任意结点x映射到某个给定范 围 [ 0 , M-1]的整数即可
判重：建立链表，将哈希函数得到的位置进行链表查询，没有找到说明不重，插入链表。
代码：
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个数字合成9位数    return v % hashsize;//确保hash函数值是不超过hash表的大小的非负整数}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）转换数字法：直接将9个数转换成一个9位数，然后利用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;}