经典题目不必多说，直接贴代码。
1 #include2 #include 3 #include 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 }