[BFS]正向BFS+hash解决八码问题

八数码问题，可以用单向广搜、双向广搜、A*、IDA等多种方法求解。具体可以参考：八数码的八境界

Description

 1  2  3  4 

 5  6  7  8 

 9 10 11 12 

13 14 15  x

 1  2  3  4    1  2  3  4    1  2  3  4    1  2  3  4 

 5  6  7  8    5  6  7  8    5  6  7  8    5  6  7  8 

 9  x 10 12    9 10  x 12    9 10 11 12    9 10 11 12 

13 14 11 15   13 14 11 15   13 14  x 15   13 14 15  x 

           r->           d->           r->

Input

1  2  3 

x  4  6 

7  5  8

1 2 3 x 4 6 7 5 8

Output

You will print to standard output either the word unsolvable’’, if the puzzle has no solution, or a string consisting entirely of the letters ‘r’, ‘l’, ‘u’ and ‘d’ that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line.

Sample Input

2  3  4  1  5  x  7  6  8

Sample Output

ullddrurdllurdruldr

题解：

本题一共仅有9！种结果，因此求解方法很多。一开始采用stl进行存储，但一直超时，后来改用hash轻轻松松就过了。判重时9！个排列如果用数组直接保存，每一位保存一个维度，数组开不了那么大。因此可以根据康托展开进行判重，每一种排列对应成一个整形数字，9！种排列一共9！个数字，提高了hash效率。此外，对于x我们暂且当做9处理，而123456789的康托展开是1，因此bfs的终止条件就设为当前状态的康拓展开是否为1。此外，由于本次采用正向bfs，而输出结果时需要输出之前的状态，string储存太慢，queue队列会丢失之前的状态，因此用数组充当队列，用pre追溯上一个状态在队列中的下标。解决代码如下：

#include<iostream>  
#include<cstdio>  
#include<string>  
#include<cstring>  
using namespace std;  
const int MAXN = 400000;  
int fac[9] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320};  
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };  
int opp[4] = { 'u','d','l','r' };  
bool vis[MAXN];  
struct node {  
    int stadus;  
    int cur[9];  
    int loc;  
    char path;  
    int pre;  
};  
node qu[MAXN];  
int cantor(int s[])  
{  
    int sum = 0;  
    for (int i = 0; i<9; i++)  
    {  
        int num = 0;  
        for (int j = i + 1; j<9; j++)  
            if (s[j]<s[i])  
                num++;  
        sum += num*fac[8 - i];  
    }  
    return sum + 1;  
}  
int bfs(node now) {  
    memset(vis, false, sizeof(vis));  
    int x, y;  
    int front = 0, end = 0;  
    node no = now;  
    qu[end++] = no;  
    vis[now.stadus] = true;  
    while (front < end) {  
        no = qu[front++];  
        x = no.loc / 3;  
        y = no.loc % 3;  
        if (no.stadus == 1)  
            return front - 1;  
        for (int i = 0; i < 4; i++) {  
            node cc = no;  
            int xx = x + dir[i][0];  
            int yy = y + dir[i][1];  
            if (xx < 3 && xx >= 0 && yy < 3 && yy >= 0) {  
                cc.cur[x * 3 + y] = cc.cur[x * 3 + y] ^ cc.cur[xx * 3 + yy];  
                cc.cur[xx * 3 + yy] = cc.cur[x * 3 + y] ^ cc.cur[xx * 3 + yy];  
                cc.cur[x * 3 + y] = cc.cur[x * 3 + y] ^ cc.cur[xx * 3 + yy];  
                cc.stadus = cantor(cc.cur);  
                if (!vis[cc.stadus]) {  
                    vis[cc.stadus] = true;  
                    cc.loc = xx * 3 + yy;  
                    cc.path = opp[i];  
                    cc.pre = front - 1;  
                    qu[end++] = cc;  
                }  
            }  
        }  
    }  
    return -1;  
}  
void show(int a) {  
    if (qu[a].pre) {  
        show(qu[a].pre);  
    }  
    printf("%c", qu[a].path);  
}  
int main() {  
    string tmp;  
    while (getline(cin, tmp)) {  
        int i = 0, cnt = 0;  
        node temp;  
        while (tmp[i]) {  
            if (tmp[i] == ' ') {  
                i++;  
                continue;  
            }  
            else if (tmp[i] == 'x') {  
                temp.loc = cnt;  
                temp.cur[cnt] = 9;  
                cnt++;  
                i++;  
            }  
            else {  
                temp.cur[cnt] = tmp[i] - '0';  
                cnt++;  
                i++;  
            }  
        }  
        temp.stadus = cantor(temp.cur);  
        int ans = bfs(temp);  
        ans != -1 ? show(ans) : printf("-1");  
        cout << endl;  
    }  
    return 0;  
}