AcWing 292. 炮兵阵地
原题链接
中等
作者:
萨满
,
2021-07-16 19:24:36
,
所有人可见
,
阅读 189
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 105, M = 1 << 10;
int n, m;
char k;
int g[N], cnt[M], f[2][M][M];
vector<int> state;
bool check(int st)
{
if (st & (st << 1)) return false;
if (st & (st << 2)) return false;
return true;
}
int count(int st)
{
int res = 0;
for (int i = 0; i < m; i ++)
res += (st >> i) & 1;
return res;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
for (int j = 0; j < m; j ++)
cin >> k, g[i] |= (k == 'H') << 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 (auto a : state)
for (auto b : state)
for (auto c : state)
{
if ((a & b) || (b & c) || (a & c)) continue;
if ((g[i] & a) || (g[i - 1] & b)) continue;
f[i&1][a][b] = max(f[i&1][a][b], f[(i - 1)&1][b][c] + cnt[a]);
}
cout << f[(n + 2)&1][0][0] << endl;
return 0;
}