「CODEVS1225」八数码问题(八数码难题)

2013年12月22日6,9510

题目描述 Description

Yours和zero在研究A*启发式算法.拿到一道经典的A*问题,但是他们不会做,请你帮他们.
问题描述

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

输入描述 Input Description

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

输出描述 Output Description

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

样例输入 Sample Input

283104765

样例输出 Sample Output

4

代码

搞了个双向搜索+康托展开，真折腾

#include<iostream>
#include<cstring>
using namespace std;
struct data{int a[3][3];}d[2][362880];//0正向搜索，1反向搜索 
int xx[4]={1,-1,0,0},yy[4]={0,0,1,-1};
int mp[2][362881],step[2][362880],flag=0;
int t[2],w[2]={1,1};
void sp(int &a,int &b){int t=a;a=b;b=t;}
bool pd(int x,int y){if(x>=3||y>=3||x<0||y<0)return 0;return 1;}
int cantor(int x){
    int fac[10]={1,1,2,6,24,120,720,5040,40320,362880},m[9]; 
    for(int i=9;i>=1;i--){m[i]=x%10;x/=10;}
    int s=0;
    for(int i=1;i<=9;i++)
    {
        int temp=0;
        for(int j=i+1;j<=9;j++)
            if(m[j]<m[i])temp++;
        s+=fac[9-i]*temp;
    }
    return s;
}
int Hash(int a[3][3]){
int x=0,k=1;
for(int i=2;i>=0;i--)
   for(int j=2;j>=0;j--)
      {x+=a[i][j]*k;k*=10;}
return cantor(x);
}
void search(int k){
     for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
           d[k][w[k]].a[i][j]=d[k][t[k]].a[i][j];
     int x,y;
     for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
           if(d[k][t[k]].a[i][j]==0){x=i;y=j;break;}
     for(int dir=0;dir<4;dir++)
     {
             for(int i=0;i<3;i++)
                for(int j=0;j<3;j++)
                   d[k][w[k]].a[i][j]=d[k][t[k]].a[i][j];
             int p=x+xx[dir],q=y+yy[dir];
             if(pd(p,q))
             { 
             sp(d[k][w[k]].a[x][y],d[k][w[k]].a[p][q]);
             int temp=Hash(d[k][w[k]].a);
             if(mp[k][temp]==-1)
             {
                    step[k][w[k]]=step[k][t[k]]+1;
                    mp[k][temp]=step[k][w[k]];   
                    if(mp[0][temp]!=-1&&mp[1][temp]!=-1)
                    {
                         cout<<mp[0][temp]+mp[1][temp];
                         flag=1;
                         return;
                         }        
                    w[k]++;
             }
         } 
     }
     t[k]++;
     }
void doit(){
     while(!flag){
     if(w[0]-t[0]<=w[1]-t[1])search(0);
     else search(1);}
}
int main(){
string str;
cin>>str;
int k=0;
for(int i=0;i<3;i++)
   for(int j=0;j<3;j++)
   {
      d[0][0].a[i][j]=str[k]-'0';
      k++;
   }
d[1][0]=(data){1,2,3,8,0,4,7,6,5};
memset(mp,-1,sizeof(mp));
mp[0][Hash(d[0][0].a)]=mp[1][Hash(d[1][0].a)]=0;
doit();
return 0;
}

#include<iostream>

#include<cstring>

using namespace std;

struct data{int a[3][3];}d[2][362880];//0正向搜索，1反向搜索

int xx[4]={1,-1,0,0},yy[4]={0,0,1,-1};

int mp[2][362881],step[2][362880],flag=0;

int t[2],w[2]={1,1};

void sp(int &a,int &b){int t=a;a=b;b=t;}

bool pd(int x,int y){if(x>=3||y>=3||x<0||y<0)return 0;return 1;}

int cantor(int x){

int fac[10]={1,1,2,6,24,120,720,5040,40320,362880},m[9];

for(int i=9;i>=1;i--){m[i]=x%10;x/=10;}

int s=0;

for(int i=1;i<=9;i++)

{

int temp=0;

for(int j=i+1;j<=9;j++)

if(m[j]<m[i])temp++;

s+=fac[9-i]*temp;

}

return s;

}

int Hash(int a[3][3]){

int x=0,k=1;

for(int i=2;i>=0;i--)

for(int j=2;j>=0;j--)

{x+=a[i][j]*k;k*=10;}

return cantor(x);

}

void search(int k){

for(int i=0;i<3;i++)

for(int j=0;j<3;j++)

d[k][w[k]].a[i][j]=d[k][t[k]].a[i][j];

int x,y;

for(int i=0;i<3;i++)

for(int j=0;j<3;j++)

if(d[k][t[k]].a[i][j]==0){x=i;y=j;break;}

for(int dir=0;dir<4;dir++)

{

for(int i=0;i<3;i++)

for(int j=0;j<3;j++)

d[k][w[k]].a[i][j]=d[k][t[k]].a[i][j];

int p=x+xx[dir],q=y+yy[dir];

if(pd(p,q))

{

sp(d[k][w[k]].a[x][y],d[k][w[k]].a[p][q]);

int temp=Hash(d[k][w[k]].a);

if(mp[k][temp]==-1)

{

step[k][w[k]]=step[k][t[k]]+1;

mp[k][temp]=step[k][w[k]];

if(mp[0][temp]!=-1&&mp[1][temp]!=-1)

{

cout<<mp[0][temp]+mp[1][temp];

flag=1;

return;

}

w[k]++;

}

t[k]++;

}

void doit(){

while(!flag){

if(w[0]-t[0]<=w[1]-t[1])search(0);

else search(1);}

}

int main(){

string str;

cin>>str;

int k=0;

for(int i=0;i<3;i++)

for(int j=0;j<3;j++)

{

d[0][0].a[i][j]=str[k]-'0';

k++;

}

d[1][0]=(data){1,2,3,8,0,4,7,6,5};

memset(mp,-1,sizeof(mp));

mp[0][Hash(d[0][0].a)]=mp[1][Hash(d[1][0].a)]=0;

doit();

return 0;

}

主程序开头的部分也可以这样写，上面的写法是得到了面包大神帥芞の面包的指导orz

string str1="123804765",str2;
cin>>str2;
int k=0;
for(int i=0;i<3;i++)
   for(int j=0;j<3;j++)
   {
      d[1][0].a[i][j]=str1[k]-'0';
      d[0][0].a[i][j]=str2[k]-'0';
      k++;
   }