八数码问题（广搜）_一、问题描述 一个九宫格,有八个数字1-8已经确定位置,剩下一个空格以0表示,0可以

题目：

描述：

在九宫格里放在1到8共8个数字还有一个是空格，与空格相邻的数字可以移动到空格的位置，问给定的状态最少需要几步能到达目标状态（用0表示空格）：
1 2 3
4 5 6
7 8 0

输入：

输入一个给定的状态。

输出：

输出到达目标状态的最小步数。不能到达时输出-1。

输入样例：

1 2 3
4 0 6
7 5 8

输出样例：

2

思想：广搜，将每一次扩展后的节点的状态用一个9位十进制数来表示，目标状态是123456780，判重用set，之后就是全裸的广搜；

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <set>
#include <stdlib.h>
using namespace std;
 
const int maxn = 400000;
const int status = 123456780;
int vis[maxn];
int dir[4] = {-1,1,-3,3};
char mapp[20];
char tmp[20];
struct state
{
    int new_status;
    int step;
};
 
int new_status(int statuss,int n)
{
    //char tmp[10];
    int zero_loc;
    sprintf(tmp,"%09d",statuss);
    for(int i = 0;i < 9;i ++)
    {
        if(tmp[i] == '0')
            zero_loc = i;
    }
    switch (n){
    case -3: //第一行
        if(zero_loc - 3 < 0) return -1;
        else
        {
            tmp[zero_loc] = tmp[zero_loc + n];
            tmp[zero_loc + n] = '0';
        }
        break;
    case 3://第3行
        if(zero_loc + 3 > 8)
            return -1;
        else {
              tmp[zero_loc] = tmp[zero_loc + n];
              tmp[zero_loc + n] = '0';
            }
            break;
    case -1: //第一列
        if(zero_loc % 3 == 0)
            return -1;
        else
        {
            tmp[zero_loc] = tmp[zero_loc + n];
            tmp[zero_loc + n] = '0';
        }
        break;
    case 1: //第三列
        if(zero_loc % 3 == 2)
            return -1;
        else
        {
            tmp[zero_loc] = tmp[zero_loc + n];
            tmp[zero_loc + n] = '0';
        }
        break;
    }
    return atoi(tmp);
}
 
int bfs(state st)
{
    queue <state> que;
    state now ,next;
    set<int>expand;
    st.step = 0;
    que.push(st);
    expand.insert(st.new_status);
    while(!que.empty())
    {
        now = que.front();
        que.pop();
        if(now.new_status == status)
        {
            return now.step;
        }
        for(int i = 0;i < 4;i ++)
        {
            next.new_status = new_status(now.new_status,dir[i]);
            next.step = now.step + 1;
            if(next.new_status == -1) //不满足
                continue;
            if(expand.find(next.new_status) != expand.end())//判重
                continue;
            expand.insert(next.new_status);
            que.push(next);
        }
    }
    return -1;
}
 
int main()
{
    int mmap[3][3];
    int t = 0;
    for(int i = 0;i < 3;i ++)
        for(int j = 0;j < 3;j ++)
    {
        cin >> mmap[i][j];
        mapp[t ++] = mmap[i][j] + '0';
    }
    //cout << mapp << endl;
    state st;
    st.new_status = atoi(mapp);
    int step = bfs(st);
    cout << step << endl;
    //cout << tmp << endl;
    return 0;
}
/*被我们qiwang老师聪明的才智所折服*/