> 代码如下
> #include <stdio.h>
> #include <string.h>
> #include <algorithm>
> #include<iostream>
> #include<cmath>
> #include<vector>
> #include<map>
> #define INF 0x3f3f3f3f
> #define MAXN 200010
> typedef long long ll;
> using namespace std;
> int a[110],dp[3][1<<10][1<<10],sum[1<<10];
> int n,m;
> void getsum()
> {
>     for(int i=0; i<(1<<m); i++)
>     {
>         int res=0,x=i;
>         while(x)
>         {
>             if(x&1)
>                 res++;
>             x>>=1;
>         }
>         sum[i]=res;
>     }
> }
> inline bool judge(int x)
> {
>     if((x&(x<<1))||(x&(x<<2)))
>         return true;
>     return false;
> }
> int main()
> {
>     cin>>n>>m;
>     getsum();
>     char ch;
>     for(int i=0; i<n; i++)
>         for(int j=0; j<m; j++)
>         {
>             cin>>ch;
>             a[i]<<=1;
>             a[i]+=(ch=='H'?1:0);
>         }
>     for(int i=0; i<(1<<m); i++)
>         if(!(judge(i)||(i&a[0])))
>             dp[0][0][i]=sum[i];
>     for(int i=0; i<(1<<m); i++)
>         for(int j=0; j<(1<<m); j++)
>             if(!(judge(i)||(i&a[0])||judge(j)||(j&a[1])||(i&j)))
>                 dp[1][i][j]=sum[i]+sum[j];
>     for(int i=2; i<n; i++)
>     {
>         for(int p2=0; p2<(1<<m); p2++)
>         {
>             if(judge(p2)||(p2&a[i-2]))
>                 continue;
>             for(int p1=0; p1<(1<<m); p1++)
>             {
>                 if(judge(p1)||(p1&a[i-1])||(p1&p2))
>                     continue;
>                 for(int cur=0; cur<(1<<m); cur++)
>                 {
>                     if(judge(cur)||(cur&a[i])||(cur&p1)||(cur&p2))
>                         continue;
>                     dp[i%3][p1][cur]=max(dp[i%3][p1][cur],dp[(i-1)%3][p2][p1]+sum[cur]);
>                 }
>             }
>         }
>     }
>     int ans=0;
>     for(int i=0; i<(1<<m); i++)
>     {
>         if(judge(i)||(i&a[n-2]))continue;
>         for(int j=0; j<(1<<m); j++)
>         {
>             if(judge(j)||(j&a[n-1])||(i&j))continue;
>             ans=max(ans,dp[(n-1)%3][i][j]);
>         }
>     }
>     cout<<ans<<endl;
> }