/*
WC2007_SC_HS
《炮兵阵营》——经典的状态压缩动态规划问题
*/
#include <stdio.h>
#include <stdlib.h>
#define maxn 300
int num[maxn],size;
int map[maxn];
int score[maxn];
int f[2][maxn][maxn];
int n,m;
inline void setbit(int &a,int b){
a|=(1<<(b-1));
}
inline int getbit(int a,int b){
return ((a&(1<<(b-1)))>0);
}
void dfs(int step,int state,int now){//Searching procedure for calculating the states that in a line
if (step>m){
num[++size]=state;
score[size]=now;
return;
}
int np=state;
dfs(step+1,state,now);
if (!((step>1 && getbit(state,step-1)) || (step>2 && getbit(state,step-2)))){
setbit(np,step);
dfs(step+1,np,now+1);
}
}
inline int fight(int a,int b){
return a&b;
}
void fill(){//Dynamic procedure
int row,i,j,k,now,last,max,res=0,tmp;
last=0;
now=1;
for (i=1;i<=size;i++){
if (fight(num[i],map[1])) continue;
for (j=1;j<=size;j++){
if (fight(num[j],map[2])) continue;
if (fight(num[i],num[j])) continue;
f[last][i][j]=score[i]+score[j];
}
}
for (row=3;row<=n;row++){
for (i=1;i<=size;i++){
if (fight(map[row],num[i])) continue;
for (j=1;j<=size;j++){
if (fight(map[row-1],num[j])) continue;
if (fight(num[i],num[j])) continue;
max=0;
for (k=1;k<=size;k++){
if (fight(map[row-2],num[k])) continue;
if (fight(num[k],num[i])) continue;
if (fight(num[k],num[j])) continue;
tmp=f[last][k][j]+score[i];
if (tmp>max) max=tmp;
}
f[now][j][i]=max;
}
}
last=now;
now=1-now;
}
for (i=1;i<=size;i++){
if (fight(map[n-1],num[i])) continue;
for (j=1;j<=size;j++){
if (fight(map[n],num[j])) continue;
if (fight(num[i],num[j])) continue;
if (f[last][i][j]>res) res=f[last][i][j];
}
}
printf("%d\n",res);
}
int onlyone(){//deal the situation N=1
if (n>1) return 0;
int i,max=0;
for (i=1;i<=size;i++){
if (fight(num[i],map[1])) continue;
if (score[i]>max) max=score[i];
}
printf("%d\n",max);
return 1;
}
int main(){
int i,j,row;
char tmp;
freopen("cannon.in","r",stdin);
freopen("cannon.out","w",stdout);
while (scanf("%d%d\n",&n,&m)!=EOF){
size=0;
for (i=1;i<=n;i++){
row=0;
for (j=1;j<=m;j++){
scanf("%c",&tmp);
if (tmp=='H') setbit(row,j);
}
map[i]=row;
scanf("\n");
}
dfs(1,0,0);
if (onlyone()) exit(0);
fill();
}
return 0;
}
WC2007_SC_HS
《炮兵阵营》——经典的状态压缩动态规划问题
*/
#include <stdio.h>
#include <stdlib.h>
#define maxn 300
int num[maxn],size;
int map[maxn];
int score[maxn];
int f[2][maxn][maxn];
int n,m;
inline void setbit(int &a,int b){
a|=(1<<(b-1));
}
inline int getbit(int a,int b){
return ((a&(1<<(b-1)))>0);
}
void dfs(int step,int state,int now){//Searching procedure for calculating the states that in a line
if (step>m){
num[++size]=state;
score[size]=now;
return;
}
int np=state;
dfs(step+1,state,now);
if (!((step>1 && getbit(state,step-1)) || (step>2 && getbit(state,step-2)))){
setbit(np,step);
dfs(step+1,np,now+1);
}
}
inline int fight(int a,int b){
return a&b;
}
void fill(){//Dynamic procedure
int row,i,j,k,now,last,max,res=0,tmp;
last=0;
now=1;
for (i=1;i<=size;i++){
if (fight(num[i],map[1])) continue;
for (j=1;j<=size;j++){
if (fight(num[j],map[2])) continue;
if (fight(num[i],num[j])) continue;
f[last][i][j]=score[i]+score[j];
}
}
for (row=3;row<=n;row++){
for (i=1;i<=size;i++){
if (fight(map[row],num[i])) continue;
for (j=1;j<=size;j++){
if (fight(map[row-1],num[j])) continue;
if (fight(num[i],num[j])) continue;
max=0;
for (k=1;k<=size;k++){
if (fight(map[row-2],num[k])) continue;
if (fight(num[k],num[i])) continue;
if (fight(num[k],num[j])) continue;
tmp=f[last][k][j]+score[i];
if (tmp>max) max=tmp;
}
f[now][j][i]=max;
}
}
last=now;
now=1-now;
}
for (i=1;i<=size;i++){
if (fight(map[n-1],num[i])) continue;
for (j=1;j<=size;j++){
if (fight(map[n],num[j])) continue;
if (fight(num[i],num[j])) continue;
if (f[last][i][j]>res) res=f[last][i][j];
}
}
printf("%d\n",res);
}
int onlyone(){//deal the situation N=1
if (n>1) return 0;
int i,max=0;
for (i=1;i<=size;i++){
if (fight(num[i],map[1])) continue;
if (score[i]>max) max=score[i];
}
printf("%d\n",max);
return 1;
}
int main(){
int i,j,row;
char tmp;
freopen("cannon.in","r",stdin);
freopen("cannon.out","w",stdout);
while (scanf("%d%d\n",&n,&m)!=EOF){
size=0;
for (i=1;i<=n;i++){
row=0;
for (j=1;j<=m;j++){
scanf("%c",&tmp);
if (tmp=='H') setbit(row,j);
}
map[i]=row;
scanf("\n");
}
dfs(1,0,0);
if (onlyone()) exit(0);
fill();
}
return 0;
}