算法入门经典_7.5八数码问题

思路：使用广度遍历的方法对空格进行移动，同时记录移动的步数，直到和目标矩阵的排列相同时退出。

简单回忆一下广度遍历：从起点开始，对所有与起点直接相连的点进行遍历，并将所遍历的存入队列中，下次遍历从队列取出结点作为新的起点。

关键点：
1，自定义一个类型state[9]，用来存储排列的每一次变化，在代码注释中称之为状态。
2，用一维数组存储其状态，不难根据其在数组中的位置计算出其在矩阵中的行竖位置。
3，移动时可能会出现越界的情况，比如（0,0）位置的空格就无法上移和左移，要注意将其处理。
4，有关判重复可以查看这篇博客：
https://blog.csdn.net/u012283461/article/details/79078653

#include<iostream>
#include<cstring>
using namespace std;


# define MAX 1000000 //得开大点，少个0没结果
typedef int state[9];

state st[MAX];
int dis[MAX];
int front=1,rear=2;
int goal[9];
int step[4][2] = {//上下左右四种移动方向
    {-1,0},
    {1,0},
    {0,-1},
    {0,1}
};

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;
}

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;
}

int bfs(){
    init_lookup_table();
    while (rear>front){
        // cout<<rear<<front<<endl;
    //判断当前状态是否是目标状态
        if(memcmp(goal, st[front], sizeof(st[front]))==0){
            printf("%d\n",dis[front]);
            return front;
        }
        //找到当前状态（st[front]）中空白（0)的位置
        int zero,zeroX,zeroY;

        for(int i=0;i<9;i++)
            if(st[front][i] == 0){
                zero = i;
                break;
            }
        zeroX = zero/3;//[0,2],X为行
        zeroY = zero%3;
        //计算新0的位置
        int New_zero, New_zeroX, New_zeroY;
        for(int i=0;i<4;i++){
            New_zeroX = zeroX + step[i][0];
            New_zeroY = zeroY + step[i][1];

            New_zero = 3*New_zeroX + New_zeroY;
            //判断移动是否合法（是否超出边界）
            if(New_zeroX<=2&&New_zeroX>=0 && New_zeroY<=2&&New_zeroY>=0){
                int newfront[9];
                memcpy(newfront,st[front],sizeof(st[front]));
                //完成移动，其实就是互换两个移动位置的值
                newfront[zero] = st[front][New_zero];//将当前状态下空白将要移动的位置 的值 赋值给新状态的空白位置
                newfront[New_zero] = st[front][zero];//将当前状态0位置的值(其实就是0)赋值给新的状态
                dis[rear] = dis[front]+1;
                memcpy(st[rear], newfront, sizeof(newfront));
                if(try_to_insert(rear))
                    rear++;//如果rear没有增加，上一步计算出来的状态将不会保存在rear中，因为会被下一步计算的状态覆盖。同样也不用担心dis[rear]值，因为它始终是上一状态的距离+1
            }
        }
        front++;
    }
    return 0;
}


int main(){
    for(int i=0;i<9;i++)
        cin>>st[front][i];
    for(int i=0;i<9;i++)
        cin>>goal[i];
    int ans = bfs();

    getchar();
    getchar();
    return 0;
}