炮兵阵地深夜求调（悬赏2个关注）

#include <bits/stdc++.h>
using namespace std;
int n,m,ans,a[105];
int f[2][1024][1024];
bool check(int s){
	return s&(s>>1)||s&(s>>2);
}
bool ck2(int s1,int s2,int s3){
	for(int i=1;i<=m;i++){
		if((s1&1)+(s2&1)+(s3&1)>1) return 0;
		s1>>=1;s2>>=1;s3>>=1;
	}return 1;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		char s[15]; scanf("%s",s+1);
		for(int j=1;j<=m;j++)
			a[i]|=(s[j]!='P'),a[i]<<=(j!=m);
	}
	for(int i=1;i<=n;i++){
		for(int s1=0;s1<(1<<m);s1++){
			if(check(s1)||s1&a[i]) continue;
			for(int s2=0;s2<(1<<m);s2++){
				if(check(s2)||s2&a[i-1]) continue;
				for(int s3=0;s3<(1<<m);s3++){
					if(check(s3)||s3&a[max(i-2,0)]) continue;
					if(!ck2(s1,s2,s3)) continue;
					f[i&1][s1][s2] = f[i&1^1][s2][s3] + __builtin_popcount(s1);
				}
			}
		}
	}
	
	for(int s1=0;s1<(1<<m);s1++)
		for(int s2=0;s2<(1<<m);s2++)
			ans += f[n&1][s1][s2];
	cout<<ans;
	return 0;
}