AcWing 292. 炮兵阵地
原题链接
中等
作者:
整天睡大觉
,
2024-04-26 09:24:23
,
所有人可见
,
阅读 2
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, M = 1 << 12;
int n, m;
int g[N];
vector<int> state;
vector<int> head[M];
int f[2][M][M];
int cnt[M];
bool check(int state){
for(int i = 0; i < m; i ++){
if((state >> i & 1) && (state >> i + 1 & 1) | (state >> i + 2 & 1))
return false;
}
return true;
}
int count(int s){
int res = 0;
for(int i = 0; i < m; i ++){
res += (s >> i & 1);
}
return res;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++)
for(int j = 0; j < m; j ++){
char c;
cin >> c;
if(c == 'H') g[i] += 1 << j;
}
for(int i = 0; i < 1 << m; i ++){
if(check(i)) state.push_back(i);
cnt[i] = count(i);
}
for(int i = 1;i <= n + 2; i ++)
for(int j = 0;j < state.size();j ++)//第i行
for(int k = 0;k < state.size();k ++)//i - 1行
for(int u = 0;u < state.size();u ++)//i - 2行
{
int a = state[j];int b = state[k];int c = state[u];
if((a & b) != 0 || (a & c) != 0 || (b & c) != 0) continue;
if((g[i] & a) != 0 || (g[i - 1] & b) != 0) continue;
f[i & 1][j][k] = max(f[i & 1][j][k], f[i - 1 & 1][k][u] + cnt[a]);
}
cout << f[n + 2 & 1][0][0] << endl;
return 0;
}