八数码问题

---

每天坚持做算法题，熟悉基本的套路，巩固语言基础，总结经验记下所学所想。

题目

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

样例输入

2 6 4 1 3 7 0 5 8

8 1 5 7 3 6 4 0 2

样例输出

31

HINT

采用BFS求解，每次保存整体状态而非坐标

代码

typedef int State[9]; //定义"状态"类型
const int maxstate = 1000000;
State st[maxstate], goal; //状态数组。所有状态都保存在这里
int dist[maxstate]; //距离数组
//如果需要打印方案，可以在这里加一个"父亲编号"数组 int fa[maxstate]
const int dx[ ] = {-1, 1, 0, 0};
const int dy[ ] = {0, 0, -1, 1};

//hash表存放状态，因为0-8的排列最多为9!=362880个
const int hashsize = 1000003;
int head[hashsize], next1[maxstate];
void init_lookup_table( ) { memset(head, 0, sizeof(head)); }
int hash1(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 = hash1(st[s]);
    int u = head[h]; //从表头开始查找链表
    while(u){
        if(memcmp(st[u],st[s], sizeof(st[s]))==0) return 0; //找到了，插入失败，book=1
        u = next1[u]; //顺着链表继续找
    }
    next1[s] = head[h]; //插入到链表中
    head[h] = s;
    return 1;//book=0
}


//BFS，返回目标状态在st数组下标
int bfs( ) {
    init_lookup_table( ); //初始化查找表,用于去重
    int front = 1, rear = 2; //不使用下标0，因为0被看作"不存在"
    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; //找"0"的位置
        int x = z/3, y = z%3; //获取行列编号（0~2）
        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)); //扩展新结点
                t[newz] = s[z];
                t[z] = s[newz];
                dist[rear] = dist[front] + 1; //更新新结点的距离值
                if(try_to_insert(rear)) rear++; //如果成功插入查找表，修改队尾指针
            }
        }
        front++; //扩展完毕后再修改队首指针
    }
    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;
}

//封装
typedef int State[9]; //定义"状态"类型
const int maxstate = 1000000;
struct StateNode{
    StateNode():dist(0){}
    State stat;
    int dist;
};
State goal; //状态数组。所有状态都保存在这里

//如果需要打印方案，可以在这里加一个"父亲编号"数组 int fa[maxstate]
const int dx[ ] = {-1, 1, 0, 0};
const int dy[ ] = {0, 0, -1, 1};

//hash表存放状态，因为0-8的排列最多为9!=362880个
const int hashsize = 1000003;
struct HashNode{
    HashNode():next(0){}
    State stat;
    HashNode* next;
};
HashNode* head[hashsize];
void init_lookup_table( ) { memset(head, 0, sizeof(head)); }
int hash1(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(StateNode s){
    int h = hash1(s.stat);
    HashNode* u = head[h]; //从表头开始查找链表
    while(u){
        if(memcmp(u->stat,s.stat, sizeof(s.stat))==0) return 0; //找到了，插入失败，book=1
        u = u->next; //顺着链表继续找
    }
    HashNode* n = new HashNode();
    memcpy(&n->stat, &s.stat, sizeof(s.stat));
    n->next = head[h];
    head[h] = n;
    return 1;//book=0
}

void deleteHash(HashNode* h[]){
    for(int i = 0; i < hashsize; ++i){
        if(!h[i]) continue;
        HashNode* cur = h[i];
        while(cur){
            HashNode* de = cur;
            cur = cur->next;
            delete de;
        }
    }
}

//BFS，返回目标状态在st数组下标
int bfs(StateNode be) {
    init_lookup_table( ); //初始化查找表,用于去重
    queue<StateNode> StatQueue;
    StatQueue.push(be);

    while(!StatQueue.empty()) {
        StateNode& s = StatQueue.front();
        if(memcmp(goal, s.stat, sizeof(s.stat)) == 0) return s.dist;//找到目标状态，成功返回
        int z;
        for(z = 0; z < 9; z++) if(!s.stat[z]) break; //找"0"的位置
        int x = z/3, y = z%3; //获取行列编号（0~2）
        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){ //如果移动合法
                StateNode t;
                memcpy(&t.stat, &s.stat, sizeof(s.stat)); //扩展新结点
                t.stat[newz] = s.stat[z];
                t.stat[z] = s.stat[newz];
                t.dist = s.dist+1; //更新新结点的距离值
                if(try_to_insert(t)) StatQueue.push(t); //如果成功插入查找表，修改队尾指针
            }
        }
        StatQueue.pop(); //扩展完毕后再修改队首指针
    }
    return 0; //失败
}


int main( ){
    StateNode sta;
    for(int i = 0; i < 9; i++) scanf("%d", &sta.stat[i]); //起始状态
    for(int i = 0; i < 9; i++) scanf("%d", &goal[i]); //目标状态

    int ans = bfs(sta); //返回目标状态的下标
    if(ans > 0) printf("%d\n", ans);
    else printf("-1\n");

    deleteHash(head);
    return 0;
}