司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

输入格式

第一行包含两个由空格分割开的正整数，分别表示N和M；

接下来的N行，每一行含有连续的M个字符（‘P’或者‘H’），中间没有空格。按顺序表示地图中每一行的数据。N≤100；M≤10。

---

 

当然本来有1024种情况，你筛一筛就只有60种

我们可以发现每一行都跟上两行有关，

这就很像scoi的扫雷

f[i][j][k]表示当前枚举到第i行，上一行的状态为j，上上行的状态为k

#include
      
       #define re return#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}int n,m,now,sum[65],sta[65],SUM,f[105][65][65];inline bool judge(int x){    if(((x<<1)&x)||((x<<2)&x))re 0;    SUM=0;    while(x)    {        if(x&1)++SUM;        x>>=1;    }        re 1;}inline void pre(){    char ss[20];    scanf("%s",ss+1);    now=0;    inc(j,1,m)    now=now*2+(ss[j]=='P');}int main(){            rd(n),rd(m);    int cnt=0;        //预处理出二进制     inc(i,0,(1<