炮兵阵地深夜求调（悬赏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;
}