You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
60 lines
1.3 KiB
60 lines
1.3 KiB
#include <bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
const int N = 110;
|
|
const int M = 1 << 10;
|
|
int n, m;
|
|
int g[N];
|
|
int cnt[M];
|
|
int f[2][M][M];
|
|
vector<int> st;
|
|
vector<int> head[M];
|
|
|
|
bool check(int x) {
|
|
return !(x & x >> 1 || x & x >> 2);
|
|
}
|
|
|
|
int count(int x) {
|
|
int res = 0;
|
|
while (x) {
|
|
x = x & (x - 1);
|
|
res++;
|
|
}
|
|
return res;
|
|
}
|
|
|
|
int main() {
|
|
scanf("%d %d", &n, &m);
|
|
for (int i = 1; i <= n; i++)
|
|
for (int j = 1; j <= m; j++) {
|
|
char c;
|
|
scanf(" %c", &c);
|
|
if (c == 'H') g[i] += 1 << (j - 1);
|
|
}
|
|
|
|
for (int i = 0; i < 1 << m; i++)
|
|
if (check(i)) st.push_back(i), cnt[i] = count(i);
|
|
|
|
for (int a : st)
|
|
for (int b : st)
|
|
if (!(a & b))
|
|
head[a].push_back(b);
|
|
|
|
for (int i = 1; i <= n; i++)
|
|
for (int a : st) {
|
|
if (g[i] & a) continue;
|
|
for (int b : head[a])
|
|
for (int c : head[b])
|
|
if (!(a & c))
|
|
f[i & 1][a][b] = max(f[i & 1][a][b], f[i - 1 & 1][b][c] + cnt[a]);
|
|
}
|
|
|
|
int res = 0;
|
|
for (int a : st)
|
|
for (int b : head[a])
|
|
res = max(res, f[n & 1][a][b]);
|
|
|
|
printf("%d\n", res);
|
|
return 0;
|
|
}
|