八数码难题 洛谷1379

洛谷1379八数码难题

题目描述

在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入输出格式

输入格式：

输入初试状态，一行九个数字，空格用0表示

输出格式：

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)

输入输出样例

输入样例#1：

283104765

输出样例#1：

4

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<queue>
using namespace std;
string st,aim=" 123804765",s,si;
char x;
map<string,int>p;
queue<string>q;
queue<int>t;
int main()
{
    cin>>st;
    st=' '+st;
    q.push(st);
    p[st]=1;
    t.push(0);
    while(!q.empty())
      {
          s=q.front();
          int step=t.front();
          t.pop();q.pop();
          if(s==aim)
            {
                cout<<step<<endl;
                return 0;
          }
        si=s;
          int pi=si.find("0");
          if(pi+3<=9)
            {
                x=si[pi+3];si[pi+3]=si[pi];si[pi]=x;
                if(p[si]==0)
                  {
                      q.push(si);t.push(step+1);
                      p[si]=1;
              }
          }
        si=s;
        if(pi-3>=1)
          {
              x=si[pi-3];si[pi-3]=si[pi];si[pi]=x;
                if(p[si]==0)
                  {
                      q.push(si);t.push(step+1);
                      p[si]=1;
              }
          }
        si=s;
        if(pi+1<=9&&pi!=3&&pi!=6)
          {
              x=si[pi+1];si[pi+1]=si[pi];si[pi]=x;
                if(p[si]==0)
                  {
                      q.push(si);t.push(step+1);
                      p[si]=1;
              }
          }
        si=s;
        if(pi-1>=1&&pi!=7&&pi!=4)
          {
              x=si[pi-1];si[pi-1]=si[pi];si[pi]=x;
                if(p[si]==0)
                  {
                      q.push(si);t.push(step+1);
                      p[si]=1;
              }
          }
      }
}

/*八个数码可能构成的状态共有9！=362880种情况，可以用宽搜的方法，每种状态用一个九位的int来存储，并确保无重复，需要开bool数组来对各种状态进行标记。于是10^8这样大的数组是空间复杂度难以接受。

而如果将八数码的所有状态合看作是一个全排列，每一种状态都是一种排列，就可以用康托展开来压缩所有状态，只需开一个大小为9！=362880的数组来存储是否出现重复情况即可。

然后康托展开求阶乘没必要一个一个循环，可以用秦九韶算法
4*4!+2*3!+2*2!=113
(((4*4+2)*3+2)*2+1)*1=113

Have[ ][ ]存储某种状态是否存在
Line[ ][ ]存储双向宽搜的状态
Last[ ][ ]存储上一种状态的编号，用来输出路径
Len[ ]存储双向宽搜的已有状态数
Mid[ ]找到的答案
Now[ ]存储当前搜索到的八数码的状态

Line[0][ ]和line[1][ ]分别为两条队列
Line[0][now[0]]，Line[1][now[1]]为队列的首元素
Line[0][len[0]]，Line[1][len[1]]为队列尾元素*/
#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 370000
int s[10],line[2][MAXN],len[2],now[2],have[2][MAXN],mid[2],last[2][MAXN],NUM;
int p;
int turn(){
    int result=0;
    for(int i=0;i<9;i++){
        result*=10;
        result+=s[i];
    }
    return result;
}
int cantor(){
    int a=0,b=0;
    for(int i=8;i>=1;i--){//从后往前枚举每个数 
        int b=s[i];
        for(int j=8;j>i;j--){//枚举这个数后面的数 
            if(s[j]<s[i])--b; 
        }
        a+=b;
        a*=i;
    }
    return a;
}
void get(int num){
    for(int i=8;i>=0;i--){
        s[i]=num%10;
        if(s[i]==0)p=i;
        num/=10;
    }
}
void go(int c,int w){
    int temp=0,num=0;
    temp=s[p];s[p]=s[p+c];s[p+c]=temp;
    ++len[w];
    line[w][len[w]]=turn();
    num=cantor();
    if(have[w][num]!=0)--len[w];
    else{
        last[w][len[w]]=now[w];
        if(have[!w][num]!=0){
            mid[w]=len[w];
            mid[!w]=have[!w][num];
        }
        else have[w][num]=len[w];
    }
    temp=s[p];s[p]=s[p+c];s[p+c]=temp;
}
void out(){
    NUM++;
    /*int cnt=0;
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            cout<<s[cnt];cnt++;
        }cout<<endl;
    }
    cout<<endl;*/
}
void out1(int num){
    if(num!=1){
        out1(last[0][num]);
        //cout<<"\n";
    }
    get(line[0][num]);
    out();
}
void out2(int num){
    get(line[1][num]);
    if(num!=mid[1])
    out();
    if(num!=1){
        //cout<<"\n";
        out2(last[1][num]);
    }
}
int main(){
    char ch[10];
    cin>>ch;
    for(int i=0;i<9;i++)
        s[i]=ch[i]-'0';
    int shu=turn();
    int kang=cantor();
    line[0][1]=shu;//正向bfs的第一个状态是初始状态 
    len[0]=1;now[0]=1;have[0][kang]=1;
    s[0]=1;s[1]=2;s[2]=3;s[3]=8;s[4]=0;s[5]=4;s[6]=7;s[7]=6;s[8]=5;
    shu=turn();
    kang=cantor();
    line[1][1]=shu;//反向bfs的第一个状态是目标状态 
    len[1]=1;now[1]=1;
    if(have[0][kang]==0)have[1][kang]=1;
    else{
        cout<<0<<endl;
    }
    while(mid[0]==0&&(now[0]<=len[0]||now[1]<=len[1])){//还没出答案，继续搜 
        while(mid[0]==0&&len[1]>=len[0]&&now[0]<=len[0]){//反向bfs的状态数多于正向bfs，就着手正向bfs 
            get(line[0][now[0]]);
            //讨论0的位置 
            if(p>=3&&mid[0]==0)go(-3,0);//在后两行，可以上移 
            if(p<=5&&mid[0]==0)go(3,0);//在前两行，可以下移 
            if(mid[0]==0&&p>=1&&(p-1)%3!=2)go(-1,0);//在右两列，可以左移 
            if(mid[0]==0&&p<=8&&(p+1)%3!=0)go(1,0);//在左两列，可以右移 
            ++now[0];
        }
        while(mid[0]==0&&len[0]>=len[1]&&now[1]<=len[1]){
            get(line[1][now[1]]);
            if(p>=3&&mid[1]==0)go(-3,1);
            if(p<=5&&mid[1]==0)go(3,1);
            if(mid[1]==0&&p>=1&&(p-1)%3!=2)go(-1,1);
            if(mid[1]==0&&p<=8&&(p+1)%3!=0)go(1,1);
            ++now[1];
        }
    }
    out1(mid[0]);
    out2(mid[1]);
    cout<<NUM-1;
}