学步园

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int state[70], tot;
int cnt[70];
int dp[103][66][66];
int n, m, M;
void init() {
	M = (1<<m);
	int i, j;
	for(i = 0; i < M; i++) {
		if(i&(i>>1)) continue;
		if(i&(i>>2)) continue;
		state[tot++] = i;
	}
	memset(cnt, 0, sizeof(cnt));
	for(i = 0; i < tot; i++) {
		for(j = state[i]; j ; j -= (j&-j))
			cnt[i]++;
	}
}
bool ok(int a, int b) {
	return !(state[a]&state[b]);
}
int a[103];
char map[103][11];
int main() {
	int i, j, k, x;
	while( ~scanf("%d%d", &n, &m)) {
		init();
		memset(a, 0, sizeof(a));
		memset(dp, -1, sizeof(dp));
		for(i = 0; i < n; i++) {
			scanf("%s", map[i]);
			for(j = 0; j < m; j++)
				if(map[i][j] == 'H')
					a[i] |= (1<<j);
		}
		for(i = 0; i < tot; i++) if(!(a[0]&state[i]))
			dp[0][0][i] = cnt[i];
		for(i = 1; i < n; i++)
			for(j = 0; j < tot; j++)
				for(k = 0; k < tot; k++) if(ok(j, k) && ~dp[i-1][j][k]) {
					for(x = 0; x < tot; x++) if(ok(x, j)&& ok(x, k) && !(a[i]&state[x]))
						dp[i][k][x] = max(dp[i][k][x], dp[i-1][j][k]+cnt[x]);
				}
		int ans = 0;
		for(i = 0; i < tot; i++)
			for(j = 0; j < tot; j++) if(ok(i, j))
				ans = max(ans, dp[n-1][i][j]);
		printf("%d\n", ans);
	}
	return 0;
}