#include #include #include using namespace std; const int N = 100; const int M = 10; const int S = 60; char row[M + 1]; // Stores each row of map int map[N]; // Bitmap of each row, 1 stands for hill int st[S], s; // All valid state int dp[N][S][S]; // dp[i][j][k] means max cnt at row i, when row i at state j and row i-1 at state k int n, m; void init_state() { s = 0; for (int i = 0; i < 1 << m; i++) { if ((i << 1) & i || (i << 2) & i) continue; st[s++] = i; } } int ones(int i) { int cnt = 0; for (; i != 0; i >>= 1) i & 1 && cnt++; return cnt; } int main() { scanf("%d %d", &n, &m); memset(map, 0, sizeof(map)); for (int i = 0; i < n; i++) { scanf("%s", row); for (int j = 0; j < m; j++) { map[i] <<= 1; if (row[j] == 'H') map[i] |= 1; } } init_state(); memset(dp, 0xFF, sizeof(dp)); for (int i = 0; i < s; i++) // Init dp[0][][] if ((map[0] & st[i]) == 0) dp[0][i][0] = ones(st[i]); for (int i = 0; i < s; i++) { // Init dp[1][][] if ((map[1] & st[i]) != 0) continue; for (int j = 0; j < s; j++) { if ((st[i] & st[j]) != 0 || dp[0][j][0] == -1) continue; dp[1][i][j] = max(dp[1][i][j], dp[0][j][0] + ones(st[i])); } } for (int i = 2; i < n; i++) { for (int j = 0; j < s; j++) { if ((map[i] & st[j]) != 0) continue; for (int k = 0; k < s; k++) { if ((st[j] & st[k]) != 0) continue; for (int l = 0; l < s; l++) { if ((st[j] & st[l]) != 0 || dp[i - 1][k][l] == -1) continue; dp[i][j][k] = max(dp[i][j][k], dp[i - 1][k][l] + ones(st[j])); } } } } int ans = 0; for (int i = 0; i < n; i++) for (int j = 0; j < s; j++) for (int k = 0; k < s; k++) ans = max(ans, dp[i][j][k]); printf("%d\n", ans); return 0; }