POJ的数据真变态。。。
思路：
dp[k][i][j]: 对于第k行，上一行的i状态，这一行的j状态所能放的最大炮兵数。
zhang[i]： 一行中的状态，对于m=10大概有60个。
vv[i][j]: 对于第i个状态，是不是可以放在第j行上
map[i][j]: 地图i行j列可不可以放炮兵
ct[i]: 对于状态i，可以放的炮兵数
dp[k][i][j]=max(dp[k-1][z][i])+ct[j];
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<string>
#include<stdlib.h>
#define INF_MAX 0x7fffffff
#define INF 999999
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node
{int u;int v;int w;bool friend operator < (node a, node b){return a.w < b.w;}
}edge[1001];
int gcd(int n,int m){if(n<m) swap(n,m);return n%m==0?m:gcd(m,n%m);}
int lcm(int n,int m){if(n<m) swap(n,m);return n/gcd(n,m)*m;}
int zhang[1200];
int vis[12000];
int ct[1200];
int map[101][11];
int dp[101][101][101];
int vv[101][101];
int k;
int n,m;
void dfs(int x,int y)
{if(vis[x]==0){int ts;ts=x;vis[x]=1;zhang[k++]=x;int s;s=0;while(x){if(x%2==1)s++;x=x/2;}ct[k-1]=s;x=ts;}if(y>m)return ;if(y>2){if(x<(1<<(y-3))){dfs(x+(1<<(y-1)),y+1);}}else if(x==0){dfs(x+(1<<(y-1)),y+1);}dfs(x,y+1);
}
void chu()
{int i,j;for(i=0;i<k;i++){for(j=0;j<n;j++){int x=zhang[i];int s;s=m-1;while(x){if(x%2==1&&map[j][s]==0)vv[i][j]=1;x=x/2;s--;}}}
}
int main()
{char st[101];int i,j;while(~scanf("%d%d%*c",&n,&m)){int mm;mm=0;k=0;mem(vis,0);mem(ct,0);mem(dp,0);mem(vv,0);dfs(0,1);for(i=0;i<n;i++){scanf("%s",st);for(j=0;j<m;j++){if(st[j]=='P')map[i][j]=1;else map[i][j]=0;}getchar();}chu();for(i=0;i<k;i++){if(vv[i][0]==0)dp[0][0][i]=ct[i];if(dp[0][0][i]>mm)mm=dp[0][0][i];}if(n<2){cout<<mm<<endl;continue;}for(i=0;i<k;i++){for(j=0;j<k;j++){if(((zhang[i]&zhang[j])==0)&&vv[j][1]==0){dp[1][i][j]=dp[0][0][i]+ct[j];}if(dp[1][i][j]>mm)mm=dp[1][i][j];}}int z,ks;for(ks=2;ks<n;ks++){for(i=0;i<k;i++){for(j=0;j<k;j++){if(((zhang[i]&zhang[j])==0)&&vv[j][ks]==0){for(z=0;z<k;z++){if((zhang[j]&zhang[z])==0)if(dp[ks][i][j]<dp[ks-1][z][i])dp[ks][i][j]=dp[ks-1][z][i];}dp[ks][i][j]+=ct[j];}if(dp[ks][i][j]>mm)mm=dp[ks][i][j];}}}cout<<mm<<endl;}return 0;
}