圣堂之地 @ 2019-08-29 20:48:38
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=105;
vector <int> v[M];//v[i]记录行数为i的所有状态
int n,m,ans,vis[1025],sum[1025],a[M],dp[101][1005][1005];//a[i]压行
//1为可以 0为不可以
inline int check(int s){return !(s&(s<<1))&&!(s&(s<<2))&&!(s&(s>>1))&&!(s&(s>>2));}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char tmp;
cin>>tmp;
if(tmp=='P') a[i]=(a[i]<<1)+1;
else a[i]<<=1;
}
}
for(int s=0;s<(1<<n);s++) //预处理
if(check(s)){
if((a[1]&s)==s) v[1].push_back(s); //第一行
bitset <10000> tmp(s);
sum[s]=tmp.count(); //计算1的个数
dp[1][0][s]=sum[s];//初始化
vis[s]=1;//这种状态在 不考虑平原山脉的情况 下可行
}
for(int s1=0;s1<(1<<m);s1++){//第二行
for(int i=0;i<v[1].size();i++){
int s2=v[1][i];//第一行状态为s1
if(!(s1&s2)&&vis[s1]&&vis[s2]&&(a[2]&s1)==s1)
v[2].push_back(s1),dp[2][s2][s1]=max(dp[2][s2][s1],dp[1][0][s2]+sum[s1]);
}//如该种状态可行,第二行加入此状态
}
for(int i=3;i<=n;i++){
for(int s=0;s<(1<<m);s++){//枚举当前状态
if(vis[s]&&(s&a[i])==s){
for(int a=0;a<v[i-1].size();a++){//枚举上一行状态
int s1=v[i-1][a];//上一行状态为s1
for(int b=0;b<v[i-2].size();b++){//枚举上两行状态
int s2=v[i-2][b];//上两行状态为s2
if((!(s&s1))&&!(s&s2)&&!(s1&s2))//互相无法炮击
v[i].push_back(s),dp[i][s1][s]=max(dp[i][s1][s],dp[i-1][s2][s1]+sum[s]);
}//这一行加入该状态
}
}
}
}
for(int a=0;a<v[n].size();a++){
int s1=v[n][a];
for(int b=0;b<v[n-1].size();b++){
int s2=v[n-1][b];
ans=max(ans,dp[n][s2][s1]);
}
}
printf("%d",ans);
return 0;
}