AcWing 292. 炮兵阵地
原题链接
中等
作者:
chenjiaqiy
,
2023-12-10 16:40:27
,
所有人可见
,
阅读 57
#include<iostream>
#include <vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 11,M = 1 << 10,mod = 1e8;
int n,m;
int g[110];
vector <int> state;
//vector<int> head[M];
int f[2][M][M],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 state)
{
int res = 0;
for (int i = 0; i < m; i ++ ) res += state >> 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); //cnt表示每一个二进制数里1的个数
}
for (int i = 1; i <= n + 2; i ++ )
for (int j = 0; j < state.size(); j ++ )
for (int k = 0; k < state.size(); k ++ )
for (int u = 0; u < state.size(); u ++ )
{
int a = state[j],b = state[k],c = state[u];
//a表示i - 1行合法状态,b表示i行,c表示i - 2行
if((a & b) | (b & c) | (a & c)) continue;
if(g[i - 1] & a | g[i] & b) continue;
f[i & 1][j][k] = max(f[i & 1][j][k],f[i - 1 & 1][u][j] + cnt[b]); //+第i行状态
}
cout << f[n + 2 & 1][0][0] << endl;
return 0;
}