1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5  6 int n, m, cnt, size; 7 int a[110], st[70], ct[70]; 8 char str[15]; 9 int f[110][70][70];10 void init()11 {12     size = 0;13     int maxn = 1 << m;14     for (int i = 0; i < maxn; i++){15         if (!(i&(i<<2)) && !(i&(i<<1))){16             st[size] = i;17             ct[size] = 0;18             int tmp = i;19             while(tmp) tmp = tmp&(tmp-1), ct[size]++;20             size++;21         }22     }23 }24 int main()25 {26     scanf("%d %d", &n, &m);27     for (int i = 1; i <= n; i++){28         scanf("%s", str);29         a[i] = 0;30         for (int j = 0; j < m; j++){31             if (str[j] == ‘H‘) a[i] |= 1 << j;32         }33     }34     init();35     memset(f, 0, sizeof(f));36     for (int j = 0; j < size; j++){37         if (!(a[1]&st[j])) f[1][j][0] = ct[j];38     }39     for (int i = 2; i <= n; i++){40         for (int j = 0; j < size; j++){41             if (a[i]&st[j]) continue;42             for (int k = 0; k < size; k++){43                 if (a[i-1]&st[k]) continue;44                 if (i == 2){45                     if (!(st[j]&st[k]))46                         f[i][j][k] = max(f[i][j][k], f[i-1][k][0] + ct[j]);47                 }48                 else for (int l = 0; l < size; l++){49                     if (!(a[i-2]&st[l]) && !(st[j]&st[k]) && !(st[j]&st[l]) && !(st[k]&st[l]))50                         f[i][j][k] = max(f[i][j][k], f[i-1][k][l] + ct[j]);51                 }52             }53         }54     }55     int ans = 0;56     for (int j = 0; j < size; j++)57         for (int k = 0; k < size; k++)58             ans = max(ans, f[n][j][k]);59     printf("%d\n", ans);60     return 0;61 }