zhangyaiwei @ 2023-06-06 21:14:22
die码:
#include<bits/stdc++.h>
using namespace std;
char Char;
bool Maps[111],C[2111];
int n,m,f[111][2111][2111];//T UP DOWN
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>Char;
Maps[i]=Maps[i]*2+(Char=='H');
}
}
for(int i=0;i<=(1<<m)-1;i++){
for(int j=0;j<m;j++){
f[1][0][i]+=bool(i&(1<<j));//统计，顺便处理仅以一行的情况
}
C[i]=!(i&((i<<1)|(i<<2)|(i>>1)|(i>>2)));//是否可用
}
for(int i=0;i<=(1<<m)-1;i++){
if(C[i]&&(!(Maps[1]&i))){
for(int j=0;j<=(1<<m)-1;j++){
if(C[j]&&(!(Maps[2]&j))&&(!(i&j))){
f[2][i][j]=max(f[2][i][j],f[1][0][i]+f[1][0][j]);//转移（仅有两行）
}
}
}
}
for(int t=3;t<=n;t++){
for(int i=0;i<=(1<<m)-1;i++){
if(C[i]&&(!(Maps[t-2]&i))){
for(int j=0;j<=(1<<m)-1;j++){
if(C[j]&&(!(Maps[t-1]&j))&&(!(i&j))){
for(int k=0;k<=(1<<m)-1;k++){
if(C[k]&&(!(Maps[t]&k))&&(!(i&k))&&(!(j&k))){
f[t][j][k]=max(f[t][j][k],f[t-1][i][j]+f[1][0][k]);//转移（三行及以上）
}
}
}
}
}
}
}
int ans=0;
for(int i=0;i<=(1<<m)-1;i++){
if(C[i]&&(!(Maps[n-1]&i))){
for(int j=0;j<=(1<<m)-1;j++){
if(C[j]&&(!(Maps[n]&j))&&(!(i&j))){
ans=max(ans,f[n][i][j]);//取答案
}
}
}
}
cout<<ans;
}pwp
by __zhuruirong__ @ 2023-06-20 20:31:01
#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 1 << 10;
int n, m;
int g[N];
int f[2][M][M];
vector<int> states, h[M];
bool check(int x) {
return !(x & x >> 1 || x & x >> 2);
}
int count(int x) {
int res = 0;
for(int i = 0; i < m; i++)
if(x >> i & 1) res++;
return res;
}
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 0; j < m; j++) {
char ch;
cin >> ch;
if(ch == 'H') g[i] += 1 << j;
}
for(int i = 0; i < 1 << m; i++)
if(check(i)) states.push_back(i);
for(auto x : states)
for(auto y : states)
if((x & y) == 0) h[x].push_back(y);
for(int i = 1; i <= n + 2; i++)
for(auto s : states)
if(!(g[i] & s))
for(auto x : h[s])
for(auto y : h[x])
if(!(s & y))
f[i&1][s][x] = max(f[i&1][s][x], f[i-1&1][x][y] + count(s));
cout << f[n + 2 & 1][0][0] << endl;
return 0;
}