Eight

Eight

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1043/http://acm.split.hdu.edu.cn/showproblem.php?pid=1043

IDA*

八数码问题直接dfs/bfs，时间复杂度很高，需要一个很好的剪枝，使用IDA*。当前状态到达目标状态最短（理想）距离h是各个数字直接到达目的地，如果h+当前步数>最深搜索的步数，那么这种情况就不去考虑。对于判断八数码是否可解，需要用到逆序数的知识（(╯‵□′)╯︵┻━┻这谁会知道啊）：x的移动并不影响整个数列逆序数的奇偶性，也就是说若给定初始状态逆序数的奇偶性与目标状态不同，则unsolvable。去重用到了状态压缩，因为数字数量级为10^9，使用set/map存储状态。（坑点是多组数据，但是题目没说）

代码如下：

  1 #include<cstdio>
  2 #include<cmath>
  3 #include<iostream>
  4 #include<set>
  5 using namespace std;
  6 const int standard=123456780;
  7 set<int>exist;
  8 int a[9],state[3][3],deep,sx,sy,step[1000];
  9 char c;
 10 int dx[]={0,0,-1,1};
 11 int dy[]={-1,1,0,0};
 12 char towards[]={'l','r','u','d'};
 13 int index;
 14 bool ok=0;
 15 int inversions(){//求逆序数
 16     int num=0;
 17     for(int i=0;i<9;++i)
 18     for(int j=i+1;j<9;++j)
 19     if(a[i]!=0&&a[j]!=0)
 20         if(a[j]<a[i])num++;
 21     return num;
 22 }
 23 int zip(){
 24     int s=0;
 25     for(int i=0;i<3;++i)
 26     for(int j=0;j<3;++j)
 27         s=s*10+state[i][j];
 28     return s;
 29 }
 30 int Astar(){//无视障碍物直接到达目的地所需步数
 31     int h=0;
 32     for(int i=0;i<3;++i)
 33     for(int j=0;j<3;++j){
 34         int num=state[i][j];
 35         if(num!=0){
 36             int x=(num-1)/3;
 37             int y=(num-1)%3;
 38             h+=abs(x-i)+abs(y-j);
 39         }
 40     }
 41     return h;
 42 }
 43 void IDAstar(int px,int py,int nowdeep){
 44     if(ok)return;
 45     int h=Astar();
 46     if(!h&&zip()==standard){
 47         ok=1;
 48         return;
 49     }
 50     if(nowdeep+h>deep)return;//A*估价函数
 51     for(int i=0;i<4;++i){
 52         int x=px+dx[i];
 53         int y=py+dy[i];
 54         if(0<=x&&x<3&&0<=y&&y<3){
 55             swap(state[px][py],state[x][y]);
 56             int s=zip();
 57             if(!exist.count(s)){
 58                 step[index++]=i;
 59                 exist.insert(s);
 60                 IDAstar(x,y,nowdeep+1);
 61                 if(ok)return;
 62                 exist.erase(s);
 63                 step[--index]=0;
 64             }
 65             swap(state[px][py],state[x][y]);
 66         }
 67     }
 68 }
 69 int main(void){
 70     char k;
 71     while(cin>>k){
 72         ok=0;
 73         index=0;
 74         for(int i=0;i<9;++i){
 75             if(i==0)c=k;
 76             else cin>>c;
 77             if('1'<=c&&c<='8')
 78                 a[i]=c-'0';
 79             else a[i]=0;
 80         }
 81         if(inversions()&1){//若有解，逆序数的奇偶性和standard相同
 82             cout<<"unsolvable"<<endl;
 83             continue;
 84         }
 85         for(int i=0;i<3;++i)
 86         for(int j=0;j<3;++j){
 87             state[i][j]=a[3*i+j];
 88             if(state[i][j]==0)
 89                 sx=i,sy=j;
 90         }
 91         int s=zip();
 92         if(s==standard){
 93             cout<<""<<endl;
 94             continue;
 95         }
 96         for(deep=1;!ok;++deep){
 97             exist.clear();
 98             exist.insert(s);
 99             IDAstar(sx,sy,0);
100         }
101         for(int i=0;i<index;++i)
102             cout<<towards[step[i]];
103         cout<<""<<endl;
104     }
105 }