Proxima_Centauri @ 2024-03-22 22:09:14
rt,感谢各位大佬
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int h[110], p[110], b[110], cnt;
int f[110][110][110];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < (1 << m); i++)
{
if ((i & (i << 1)) || (i & (i << 2))) continue;
p[++cnt] = i;
int t = i;
while (t)
{
b[cnt] += t & 1;
t >>= 1;
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
char c;
scanf(" %c", &c);
h[i] <<= 1;
h[i] += (c == 'H');
}
for (int j = 1; j <= cnt; j++)
{
if (p[j] & h[1]) continue;
else f[1][j][1] = b[j];
}
for (int i = 2; i <= n; i++)
for (int j = 1; j <= cnt; j++)
{
if (p[j] & h[i]) continue;
for (int k = 1; k <= n; k++)
{
if (p[k] & h[i - 1]) continue;
if (p[k] & p[j]) continue;
for (int l = 1; l <= n; l++)
{
if (p[l] & h[i - 2]) continue;
if (p[l] & p[k]) continue;
if (p[l] & p[j]) continue;
f[i][j][k] = max(f[i][j][k], f[i - 1][k][l] + b[j]);
}
}
}
int ans = 0;
for (int j = 1; j <= cnt; j++)
for (int k = 1; k <= cnt; k++)
ans = max(ans, f[n][j][k]);
printf("%d\n", ans);
return 0;
}