BFS 八数码问题_牛客博客

写在前面：
做这个题目花了我不少时间写这个只是为了自己方便理解

简单来说八数码问题就是一个九宫格除了一个空着的格子以外其他都有1到8之间的一个数然后从一个状态移到另一个状态
举个例子：
图片说明

原： 1  2  3                 目标：1     3
        8  4                       8  2  4 
     7  6  5                       7  6  5

然后我们要把原这个给九宫格转化为目标九宫格，显而易见，只要把8向左移然后再把2向下移这样就可以实现转换，如何用代码实现，这里采取用bfs的做法，对空格进行搜索，相当于将空格与周围的数字进行交换。
首先是一个比较简单的题目，单纯的计算移动次数。

指定初始棋盘和目标棋盘，计算最少的移动步数

输入样例
1 2 3 0 8 4 7 6 5
输出样例
2
请在这里输入引用内容

对于八数码问题，最消耗时间的便是重复的状态，因此需要有效的判重方法这里使用的是康托展开，康托展开由我自己描述便是有一个数假如是四位数由1234组成，那么最小的就是1234最大的是4321，现在我们有一个数字2143，我们计算他是在这些数字中排到第多少大，接下来就是康托展开的原理：

首先我们看第一位，也就是位于首位的2，计算所有首位小于2的排列，这里小于2的数字只有1，所以排列有1234，1243，1324，1342，1423，1432，六个即为3✖2✖1也就是3！✖1；
然后看第二位即当第一位是2，取第二位小于1的所有排列，也就是0✖2！；
然后看第三位即当前两位是21，取第三位小于4的所有排列，这里小于4的仅有3，也就是1✖1！；
求和3！✖1+0✖2！+1✖1！=7；
因此在2143前面的数有7个，所以2143是第8大的数，因此我们可以用这个做法在碰到这个数字事快速检索到当前数字的位置对他进行判重，这里可以开一个数组进行判重的标记。
这里附上康托展开的代码

const int LEN=362880;                       //9个数共有9！也就是362880种排列
int visted[LEN]={0};                            //用来储存每一个状态是否被标记
long int factory[]={1,1,2,6,24,120,720,5040,40320,362880};     //这个是每一个阶乘的值即一到九的阶乘 
bool Cantor(int str[],int n){
    long long result;
    for(int i=0;i<n;++i){
        int counted=0;
        for(int j=i+1;j<n;++j){                 //这里计算当前未出现的元素排在第几个；
            if(str[i]<str[j])
                ++counted;
        }
        result+=counted*factory[n-i-1];           
    }
    if(!visted[result]){
        visted[result]=1;
        return 1;
    }
    else
        return 0;
}

这里附上完整代码，因为是我在书上看到的，所以我也没找到在线的oj，

应该没有比较难以理解的地方
#include<bits/stdc++.h>
using namespace std;
const int LEN=362880;
struct node{
    int state[9];
    int dis;
};

int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};             
int visited[LEN]={0};
int start[9];                   //初始位置
int goal[9];                    //目标位置
long int factory[ ]={1,1,2,6,24,120,720,5040,40320,362880};

bool Canter(int str[],int n){
    long result=0;
    for(int i=0;i<n;++i){
        int counter=0;
        for(int j=i+1;j<n;++j){
            if(str[i]>str[j])
                ++counter;
        }
        result+=counter*factory[n-i-1];
    }
    if(!visited[result]){
        visited[result]=1;
        return 1;
    }
    else
        return 0;
}

int bfs(){
    node head;
    memcpy(head.state,start,sizeof(head.state));
    head.dis=0;
    queue<node>q;
    Canter(head.state,9);
    q.push(head);
    while(!q.empty()){
        head=q.front();
        q.pop();
        int z;
        for(z=0;z<9;++z){
            if(head.state[z]==0){
                break;
            }
        }
        int x=z%3;
        int y=z/3;
        for(int i=0;i<4;++i){
            int newx=x+dir[i][0];
            int newy=y+dir[i][1];
            int newz=newx+3*newy;
            if(newx>=0&&newx<3&&newy>=0&&newy<3){
                node newnode;
                memcpy(&newnode,&head,sizeof(struct node));
                swap(newnode.state[z],newnode.state[newz]);
                newnode.dis++;
                if(memcmp(newnode.state,goal,sizeof(goal))==0)
                    return newnode.dis;
                if(Canter(newnode.state,9))
                    q.push(newnode);
            }

        }
    }
    return -1;
}

int main(void){
    for(int i=0;i<9;++i) cin>>start[i];
    for(int i=0;i<9;++i) cin>>goal[i];
    int num=bfs();
    if(num!=-1)
        cout<<num<<endl;
    else
        cout<<"Impossible"<<endl;
    return 0;
}

然后是poj上的一道题poj1077
目前我还没有做出来，自己比较菜是一个原因，还有一个原因就是这几天没有怎么写代码，我好菜，我是罪人，这个poj上的题就是在原来的移动找最快的基础上要求输出走的路径，我个人觉得要不就格外在结构体中加入一个保存路劲的字符，或者是在bfs后反过来走一次，自然反过来这一次几乎不会占用时间，走标记好的路线就行，嗯，今天就写到这，今天又是咸鱼的一天。
咸鱼写完了，咸鱼写的代码太辣眼了，勉强过了，这里附上代码

#include<bits/stdc++.h>
#define ms(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+7;
const int MAXN = 1e6+10;
#define AIM  1     //123456789的哈希值为1

struct node
{
    int status;
    int s[9];
    int loc;
};

int vis[MAXN], fac[9] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320};
int dir[4][2] = { -1,0, 1,0, 0,-1, 0,1 };
char op[4] = {'u', 'd', 'l', 'r'  };
char path[MAXN];
int pre[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;
}

queue<node>que;
bool bfs(node now)
{
    ms(vis,0);
    while(!que.empty()) que.pop();

    now.status = cantor(now.s);
    pre[now.status] = -1;   //开始状态的上一个状态为-1，用于输出路径时“刹车”
    vis[now.status] = 1;
    que.push(now);

    node tmp;
    while(!que.empty())
    {
        now = que.front();
        que.pop();
        if(now.status==AIM) //找到了123456789的状态
            return true;

        int x = now.loc/3;
        int y = now.loc%3;
        for(int i = 0; i<4; i++)
        {
            int xx = x + dir[i][0];
            int yy = y + dir[i][1];
            if(xx>=0 && xx<=2 && yy>=0 && yy<=2)
            {
                tmp = now;
                tmp.s[x*3+y] = tmp.s[xx*3+yy];  //交换位置，下同
                tmp.s[xx*3+yy] = 9;
                tmp.status = cantor(tmp.s);
                if(!vis[tmp.status])
                {
                    vis[tmp.status] = 1;
                    tmp.loc = xx*3+yy;
                    pre[tmp.status] = now.status;   //tmp.status的上一个状态为now.status
                    path[tmp.status] = op[i];   //保存操作
                    que.push(tmp);
                }
            }
        }
    }
    return 0;
}

void Print(int status)
{
    if(pre[status]==-1) return;
    Print(pre[status]);     //追溯上一个状态
    putchar(path[status]);
}

int main()
{
    char str[50];
    while(gets(str))
    {
        node now;
        int cnt = 0;
        for(int i = 0; str[i]; i++)
        {
            if(str[i]==' ') continue;
            if(str[i]=='x') now.s[cnt] = 9, now.loc = cnt++;
            else  now.s[cnt++] = str[i]-'0';
        }
        if(!bfs(now))
            puts("unsolvable");
        else
            Print(AIM), putchar('\n');
    }
    return 0;
}