JZYZOJ 1385 拉灯游戏 状态压缩 搜索

http://172.20.6.3/Problem_Show.asp?id=1385

 

刚开始想的时候一直以为同一排不同的拉灯顺序对结果是有影响的，手推了好多遍才发现拉灯结果只和拉的灯有关，这也要打表，可以说非常智障了。

如果从上向下寻找拉的灯，那么每一排全暗主要相关的是下一排（通过下一排补齐）和初始状态，而每一排的初始状态是和其本身和上一排有关的，那么只要找出第一排所有的拉灯方案（2^5种）然后对这几种方案模拟一遍找能全亮且步数最小的方案。

锻炼搜索能力的好题 

注意小于6步…交的时候没看见，日常眼瞎1/1。

 

代码

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 using namespace std;

 const int maxn=(<<)+;

 int a[]={};

 char ch[]={};

 int f[maxn]={};//第一行操作数量

 int f1[maxn]={};//第一行操作对第二行的影响

 int nn[maxn]={};//第一行操作后得到的数

 //以上三个通过dfs计算

 int aa[maxn]={};//下一行来填满这一行对下一行的影响

 int bb[maxn]={};//对下下一行的影响

 int z[maxn]={};//操作数量

 //以上三个预处理

 int ma=maxn-;

 void dfs1(int k,int num,int d,int z){

     if(k>=){

         f[z]=d;f1[z]=z;nn[z]=num;

         return;

     }

     int w=<<k,w1;

     if(k>=)w1=(<<(k-))&ma;

     else w1=/;

     dfs1(k+,num,d,z);

     dfs1(k+,num^w1,d+,z^w);

 }

 int main(){

     //freopen("wtf.in","r",stdin);

     //freopen("wtf.out","w",stdout);

     int T;scanf("%d",&T);

     for(int i=;i<=ma;i++){

         int k=;

         for(int j=;j<=;j++){

             int w=<<k,w1;

             if(k>=)w1=(<<(k-))&ma;

             else w1=/;

             if((i&w)==) aa[i]=aa[i]^w1,z[i]++;

             k--;

         }

         bb[i]=(~i)&ma;

     }

     while(T-->){

         memset(a,,sizeof(a));

         for(int i=;i<=;i++){

             scanf("%s",&ch);

             for(int j=;j<=;j++){

                 a[i]*=;

                 a[i]+=ch[j-]-'';

             }

         }memset(f,,sizeof(f));

         int da=f[];

         dfs1(,a[],,);

         int ans=da;

         for(int i=;i<=ma;i++){

             int nex1=aa[nn[i]],nex2=bb[nn[i]],bu=f[i]+z[nn[i]],num=f1[i],zz;

             for(int j=;j<=;j++){

                 num=num^a[j]^nex1;//初始状态

                 nex1=aa[num];//填满需要几步

                 if(j==&&num==ma)ans=min(ans,bu);

                 bu+=z[num];

                 zz=nex2;nex2=bb[num];num=zz;//填满这一行对下下一行的影响

             }

         }

         if(ans>)printf("%d\n",-);

         else printf("%d\n",ans);

     }

     return ;

 }