至于为什么相邻两列之间的左下攻击右下攻击不需要判断X，相信大家想一下都能想到。
下面贴代码。
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define Max 2505
#define ll long long
#define PI acos(-1.0)
#define inf 0x7fffffff
#define LL(x) ( x << 1 )
#define bug puts("here")
#define PII pair
#define RR(x) ( x << 1 | 1 )
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
using namespace std;
inline void RD(int &ret) {
char c;
do {
c = getchar();
} while(c < '0' || c > '9') ;
ret = c - '0';
while((c=getchar()) >= '0' && c <= '9')
ret = ret * 10 + ( c - '0' );
}
inline void OT(int a) {
if(a >= 10)OT(a / 10) ;
putchar(a % 10 + '0') ;
}
#define N 190
int n , m ;
char Map[1001][15] ;
int M[1001] ;
int st[N][1001] ;
int top ;
int Count[N][1001] ;
int num[1001] ;
//int dp[1111][N][N] ;
int dp [N][N] ;
void init() {
mem(M ,0) ;
mem(st ,0) ;
top = 0 ;
mem(Count ,0) ;
mem(dp ,0) ;
mem(num ,0) ;
}
void ok() {
for (int i = 0 ; i < n ; i ++ ) {
for (int j = 0 ; j < 1 << m ; j ++ ) {
int d = 0 ;
bool flag = 0 ;
for (int k = 0 ; k < m ; k ++ ) {
if(j & (1 << k)) {
if(Map[i][k] == 'X') {
flag = 1 ;
break ;
}
if(d > 2) {
flag = 1 ;
break ;
}
d = 4 ;
} else {
if(Map[i][k] == 'X') {
d = 0 ;
continue ;
}
d -- ;
}
}
if(flag)continue ;
int tt = j ;
int nn = 0 ;
while(tt) {
nn += tt % 2 ;
tt /= 2 ;
}
// cout << j << endl;
st[num[i]][i] = j ;
Count[num[i] ++ ][i] = nn ;
}
}
}
int main() {
while(cin >> n >> m , ( n + m )) {
init() ;
for (int i = 0 ; i < n ; i ++ ) {
scanf("%s",Map[i]) ;
for (int j = 0 ; j < m ; j ++ ) {
if(Map[i][j] == 'X')M[i] += (1 << j) ;
}
// cout << M[i] << endl;
}
ok() ;
int ans = 0 ;
//预处理第0行
for (int i = 0 ; i < num[0] ; i ++ ) {
if(st[i][0] & M[0])continue ;
dp[0][0][i] = Count[i][0] ;
ans = max(ans ,dp[0][0][i]) ;
}
//预处理第1行
for (int i = 0 ; i < num ; i ++ ){
if(st[i] & M )continue ;
for (int j = 0 ; j < num[0] ; j ++ ){
if(st[j][0] & st[i] )continue ;
if(st[j][0] >> 1 & st[i] )continue ;
if(st[j][0] << 1 & st[i] )continue ;
dp [j][i] = max(dp [j][i] , dp[0][0][j] + Count[i] ) ;
}
}