1449：【例题2】魔板-白红宇

1449：【例题2】魔板

阅读量：5333 次

发布时间：2019-06-15

本文共 1167 字，大约阅读时间需要 3 分钟。

题解

这道题是一道非常典型的BFS题目,BFS所面临的最大问题是判断重复。显然,如果每次判

断重复都扫描一次队列,搜索的效率将非常低,会提高一个指数级,所以一般宽度搜索的判断重复

都是运用数组来实现的,那么数组下标就需要用一个Hash函数来计算出来。

本题Hash函数的设计:我们很容易想到将8个数字按顺时针顺序组合成8进制(每个数字都

减1)的8位基数。但是,这里最大的八进制数76543210,转换成十进制数是16434824,也就是说要

开大小为16434824的数组,如果题目强制空间限制,那么,数组的下标会越界

这里我们引入康托展开,即将一个排列对应成它在全排列中的序数,这样就不会MIE了

引入

设step[ ]记步数;记 i 的父结点为prt[ i ] ; a[ i ]表示第i个序列采用哪种变换。

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
                using namespace std;int jc[10]={ 1,1,2,6,24,120,720,5040};int g,st,prt[50005],b[1000001]={ 0},step[50005];char a[50005];struct mb{ int a[2][4];}start,goal,q[90001];int Turn(mb x) //康托展开 { int i,j,res=0,t[8],s; for(i=0;i<4;i++) t[i]=x.a[0][i]; //构成序列 for(i=3;i>=0;i--) t[7-i]=x.a[1][i]; for(i=0;i<8;i++) { s=0; for(j=i+1;j<=7;j++) if(t[j]
               
                =0;i--) start.a [1][i]=8-i; st=Turn(start); //标记起始状态 b[st]=1; for(i=0;i<4;i++) cin>>goal.a [0][i]; for(i=3;i>=0;i--) cin>>goal.a [1][i]; g=Turn(goal); if(g==st) { cout<<0; return 0; } Bfs(); return 0;}