|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 110;
|
|
|
const int M = 1 << 10;
|
|
|
int n, m; // n行m列，n<=100,m<=10,注意：状态压缩DP对列的长度很敏感，太大不行
|
|
|
int g[N]; // 记录每一列的山地情况，是一个二进制标识转化后的十进制数，最大就是全都是1，也就是2^m-1
|
|
|
int cnt[M];
|
|
|
int f[N][M][M];
|
|
|
vector<int> st;
|
|
|
vector<int> head[M];
|
|
|
|
|
|
// 检查一个状态是不是合法状态[同一行必须隔两个及两个以上才是安全的]
|
|
|
bool check(int x) {
|
|
|
return !(x & x >> 1 || x & x >> 2);
|
|
|
}
|
|
|
|
|
|
// 统计某个状态中数字1的数量
|
|
|
int count(int s) {
|
|
|
int res = 0;
|
|
|
for (int i = 0; i < m; i++) // 遍历每一列
|
|
|
if (s >> i & 1) res++; // 如果此个位置数字是1，那么总的数量++
|
|
|
return res;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
// 输入
|
|
|
scanf("%d %d", &n, &m);
|
|
|
for (int i = 1; i <= n; i++) // n行
|
|
|
for (int j = 1; j <= m; j++) { // m列
|
|
|
char c;
|
|
|
scanf(" %c", &c); // 注意scanf输入char的时候，前面要加一个空格
|
|
|
if (c == 'H') g[i] += 1 << (j - 1); // 山地上不能够部署炮兵部队
|
|
|
}
|
|
|
// 1、预处理所有合法状态[单行合法即可]
|
|
|
for (int i = 0; i < 1 << m; i++)
|
|
|
if (check(i)) st.push_back(i), cnt[i] = count(i); // 预算出每个状态i里有多少个数位是1
|
|
|
|
|
|
// 2、找出所有合法状态的合法转移[行间状态兼容检测]
|
|
|
for (int a : st)
|
|
|
for (int b : st)
|
|
|
if (!(a & b)) // 上下行间不能存在同列的1
|
|
|
head[a].push_back(b);
|
|
|
// 3、dp
|
|
|
for (int i = 1; i <= n; i++) // 枚举每一行
|
|
|
for (int a : st) { // 枚举i行的每个状态
|
|
|
if (g[i] & a) continue; // 按i这样摆，确实是本行内不冲突，但如果准备放大炮的位置是高地，是不行的。
|
|
|
for (int b : head[a]) // 枚举第i-1行的每个可能状态,b肯定与a不冲突
|
|
|
for (int c : head[b]) // 枚举第i-2行的每个可能状态,c肯定是与b不冲突的
|
|
|
if (!(a & c)) // 如果c也与a不冲突的话,才是三行间完全兼容的方案
|
|
|
f[i][a][b] = max(f[i][a][b], f[i - 1][b][c] + cnt[a]);
|
|
|
}
|
|
|
|
|
|
// 4、枚举最终的状态最大值
|
|
|
int res = 0;
|
|
|
for (int a : st)
|
|
|
for (int b : head[a])
|
|
|
res = max(res, f[n][a][b]);
|
|
|
|
|
|
// 5、输出
|
|
|
printf("%d\n", res);
|
|
|
return 0;
|
|
|
}
|
