1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5  6 using namespace std ; 7  8 int dp[110][70][70] ; 9 int sum[150] ;10 int sta[110] ;11 int mapp[110] ;12 char sh[110][20] ;13 int num ;14 int N,M ;15 16 int getsum(int x)17 {18     x=(x& 0x55555555)+((x>>1)& 0x55555555);19     x=(x& 0x33333333)+((x>>2)& 0x33333333);20     x=(x& 0x0F0F0F0F)+((x>>4)& 0x0F0F0F0F);21     x=(x& 0x00FF00FF)+((x>>8)& 0x00FF00FF);22     x=(x& 0x0000FFFF)+((x>>16)& 0x0000FFFF);23     return x;24 }25 //int getsum(int x)26 //{27 //    int cnt = 0 ;28 //    while(x)29 //    {30 //        cnt ++ ;31 //        x &= x-1 ;32 //    }33 //    return cnt ;34 //}35 int main()36 {37     while(~scanf("%d %d",&N,&M) )38     {39         memset(dp,-1,sizeof(dp)) ;40         num = 0 ;41         for(int i = 1 ; i <= N ; i++)42         {43             scanf("%s",sh[i]) ;44             for(int j = 0 ; j < M ; j++)45             {46                 if(sh[i][j] == ‘H‘)47                     mapp[i] |= (1 << j) ;//把高原的地方标记一下48             }49         }50         for(int i = 0 ; i < (1 << M) ; i++)//枚举所有可行的状态51         {52             if(i & (i << 1) || i & (i >> 1) || i & (i << 2) || i & (i >> 2))53                 continue ;54         //    cout<<i<<" ";55             sum[num] = getsum(i) ;//求i状态中1的个数56             sta[num++] = i ;//将该状态存到数组中57         }58        // cout<<endl;59         for(int i = 0 ; i < num ; i++)60         {61             if(sta[i] & mapp[1]) continue ;62             dp[1][0][i] = sum[i] ;63         }64         for(int i = 2 ; i <= N ; i++)65         {66             for(int k = 0 ;k < num ; k++)67             {68                 if(mapp[i] & sta[k]) continue ;69                 for(int j = 0 ; j < num ; j++)70                 {71                     if(sta[j] & sta[k]) continue ;72                     for(int h = 0 ; h < num ; h++)73                     {74                         if(sta[h] & sta[k]) continue ;75                         if(sta[h] & sta[j]) continue ;76                         if(dp[i-1][h][j] != -1)77                         {78                             dp[i][j][k] = max(dp[i][j][k],dp[i-1][h][j]+sum[k]) ;79                         }80                     }81                 }82             }83         }84         int ans = 0 ;85         for(int j = 0 ; j < num ; j++)86         {87             for(int k = 0 ; k < num ; k++)88                 ans = max(ans,dp[N][j][k]) ;89         }90         printf("%d\n",ans) ;91     }92     return 0 ;93 }