ZOJ 3466 The Hive II （插头DP，变形）

题意：有一个n*8的蜂房（6边形的格子），其中部分是障碍格子，其他是有蜂蜜的格子，每次必须走1个圈取走其中的蜂蜜，在每个格子只走1次，且所有蜂蜜必须取走，有多少种取法？

思路：

　　以前涉及的只是n*m的矩阵，也就是四边形的，现在变成了6边形，那么每个格子也就有6个方向可以出/进。为了方便考虑，将蜂房变成按列来扫，那么轮廓线需要2*n+1个插头信息。这里不需要用到括号表示法或者最小表示法，只需要表示该位置是否有线即可，所以每个插头仅需1个位就可以表示了。

　　转置一下后的蜂房应该是这样的：

　　轮廓线是一个左，一个左上，一个右上来组成的。当前格子为奇数行时，状态需要左移2位，因为有两个方向（左，左上）是空出来的。其他的只需要根据奇偶数行来判断即可。

2700ms+

 #include <bits/stdc++.h>

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #define pii pair<int,int>

 #define INF 0x3f3f3f3f

 #define LL long long

 using namespace std;

 const int N=;

 int g[N][N], cur, n, m;

 struct Hash_Map

 {

     static const int mod=;

     static const int NN=; //至少50万

     int head[mod];       //桶指针

     int next[NN];        //记录链的信息

     LL  status[NN];      //状态

     LL  value[NN];       //状态对应的DP值。

     int size;

     void clear()    //清除哈希表中的状态

     {

         memset(head, -, sizeof(head));

         size = ;

     }

     void insert(LL st, LL val)  //插入状态st的值为val

     {

         int h = st%mod;

         for(int i=head[h]; i!=-; i=next[i])

         {

             if(status[i] == st) //这个状态已经存在，累加进去。

             {

                 value[i] += val;

                 return ;

             }

         }

         status[size]= st;           //找不到状态st，则插入st。

         value[size] = val;

         next[size] = head[h] ;      //新插入的元素在队头

         head[h] = size++;

     }

 }hashmap[];

 inline int getbit(LL s,int pos)

 {

     return ((s>>pos)&);

 }

 inline LL setbit(LL s,int pos,int bit)

 {

     s&=~((LL)<<pos);

     return (s|(LL)bit<<pos);

 }

 void DP(int i,int j)

 {

     for(int k=; k<hashmap[cur^].size; k++)

     {

         LL s=hashmap[cur^].status[k];

         LL v=hashmap[cur^].value[k];

         int R=getbit(s,*j), DL=getbit(s,*j+), DR=getbit(s,*j+);

         LL t=(setbit(s,*j+,)&setbit(s,*j+,)&setbit(s,*j+,));

         if(g[i][j]==)  //必走格子

         {

             if( R && DL && DR )   continue;   //3个插头，冲突了。

             if( R && DL || R && DR || DL && DR )    hashmap[cur].insert(t,v);   //合并

             else if( R || DL || DR )    //延续

             {

                 if( j+<m )    hashmap[cur].insert(setbit(t,*j+,), v);       //右

                 if( i+<n )

                 {

                     if( !(i&) || j+<m  ) hashmap[cur].insert(setbit(t,*j+,), v);   //右下

                     if(  (i&) || j> )    hashmap[cur].insert(setbit(t,*j+,), v);   //左下

                 }

             }

             else    //新插头

             {

                 if(i+<n)

                 {

                     if( (j>&&!(i&)) || (j+<m&&(i&)) )   //（左下，右下）

                         hashmap[cur].insert( setbit(s,*j+,)|setbit(s,*j+,), v);

                     if( j+<m )

                     {

                         if( (i&) || j> )     //（左下，右）

                             hashmap[cur].insert( setbit(s,*j+,)|setbit(s,*j+,), v);

                         if( !(i&)  || j+<m )   //（右下，右）

                             hashmap[cur].insert( setbit(s,*j+,)|setbit(s,*j+,), v);

                     }

                 }

             }

         }

         else if(R+DL+DR==)    hashmap[cur].insert(s,v); //障碍格子

     }

 }

 void cal()

 {

     cur=;

     hashmap[cur].clear();

     hashmap[cur].insert(,);

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

     {

         if( !(i&) )    //只有奇数行才需要左移

         {

             for(int k=; k<hashmap[cur].size; k++)    hashmap[cur].status[k]<<=;

         }

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

         {

             cur^=;

             hashmap[cur].clear();

             DP(i,j);

         }

     }

 }

 LL print()

 {

     for(int i=; i<hashmap[cur].size; i++)

         if(hashmap[cur].status[i]==)

             return hashmap[cur].value[i];

     return ;

 }

 int main()

 {

     freopen("input.txt", "r", stdin);

     while(~scanf("%d%d",&n,&m))

     {

         memset(g, , sizeof(g));

         char c1,c2;

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

         {

             c1=getchar();

             while(!isalpha(c1)) c1=getchar();

             c2=getchar();

             while(!isalpha(c2)) c2=getchar();

             g[c2-'A'][c1-'A']=;    //1为障碍格子

         }

         m=;

         swap(n,m);

         for(int i=; i*<n; i++)

         {

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

                 swap(g[i][j],g[n--i][j]);

         }

         cal();

         printf("%lld\n", print() );

     }

     return ;

 }

AC代码

巴特西

ZOJ 3466 The Hive II （插头DP，变形）

最新文章

热门文章