洛谷OJ P1379 八数码难题 解题报告

by MedalPluS

  题目描述

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

  输入格式

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

  输出格式

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

  分析

  其实就是个裸的BFS，但是可以拓展很多知识点（有人说不做这题的人的OI人生不完美）

  暴力BFS的话会被卡，因为要搜索的状态实在太多了

  所以这里有两种优化：

  1.启发式搜索

  我们假设f=g+h,那么g可以设为已经挪动的步数，h为不在位将牌个数，这样就构建了一个估价函数

  然后直接写就好

  2.双向BFS

  我们知道起点和终点，直接双向就好

  另外，这里应该如何判重呢？其实很简单，下面引入康托展开：

  然后就利用康托值进行判重就好

 

  代码

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 using namespace std;  6   7 #define rep(i,l,r) for(i=l;i<=r;i++)  8 const int maxn=10;  9 const int maxm=1000001;//9!*8+8!*7...<=5000001 10  11 struct node{ 12     int a[maxn][maxn]; 13     short int g; 14     node(){g=0;} 15 }Head,Tail; 16  17 short int vis_f[maxm],vis_b[maxm]; 18 int tmps[maxn]; 19 queue
         
           f,b; 20  21 int fact(int x){ 22     int ans; 23     for(ans=1;x>=2;x--)ans*=x; 24     return ans; 25 } 26  27 int Cantor(node now){
   //Cantor_Expand 28     int i,j,t=0,res=0; 29     rep(i,1,3) 30       rep(j,1,3) 31         tmps[t++]=now.a[i][j]; 32     t=0; 33     rep(i,0,8) 34     { 35         t=0; 36         rep(j,i+1,8) 37           if(tmps[j]
          
           0){ 80 swap(tmp.a[sx-1][sy],tmp.a[sx][sy]); 81 tmp.g++; 82 if(vis_b[Cantor(tmp)]!=-1){cout<
           
            0){100 swap(tmp.a[sx][sy-1],tmp.a[sx][sy]);101 tmp.g++;102 if(vis_b[Cantor(tmp)]!=-1){cout<
            
             0){135 swap(tmp.a[sx-1][sy],tmp.a[sx][sy]);136 tmp.g++;137 if(vis_f[Cantor(tmp)]!=-1){cout<
             
              0){155 swap(tmp.a[sx][sy-1],tmp.a[sx][sy]);156 tmp.g++;157 if(vis_f[Cantor(tmp)]!=-1){cout<
              
               len2){182 if(len2)expand_b();183 expand_f();184 }185 else {186 if(len1)expand_f();187 expand_b();188 }189 }190 }191 192 int main(){193 init();194 double_BFS();195 return 0;196 }
              
             
            
           
          
         
        
       
      
     

 

代码量比较大，竟然有个小200....