A了一整天~~~終於搞掉了。
真是血都A出來了。
題目意思很清楚，肯定是狀壓DP。
我們可以聯系一下POJ 1185 炮兵陣地，經典的狀壓DP。
兩道題的區別就在於，這道題的攻擊是可以被X擋住的，而且攻擊的范圍不同。
這是這道題的攻擊范圍。
但是這個攻擊范圍是會被X擋住的。
所以得在1185上加以改進。
分析：
POJ 1185，因為可以隔著障礙物打，所以他每行的狀態是一樣的，但是這題由於攻擊會被擋住，所以每行的狀態是不一樣的，所以我們預處理的時候就要處理出每一行的狀態數，分別保存，然後存下每行每個狀態的數量。
因為我的下標是從0開始的，所以我得預先處理一下第0行和第1行的狀態轉移過程，這個很好處理，具體看代碼。
那麼預處理完畢之後就是狀態轉移的過程。
變量定義：
M[i] ：每一行的地圖壓縮。
st[i][j] ：第j行，第i個狀態。
Count[i][j] ：第j行第i個狀態的數量。
num[i]：第i 行狀態的總數。
dp[i][j][k] ：第i行的狀態是k ,第i - 1 行的狀態是j的可行狀態總數。
這道題貌似還卡內存，必須使用滾動數組，因為狀壓的時候他只需要3個狀態，所以這裡i開到3就可以了。
狀態轉移的過程，首先當前狀態是k ,上一狀態是j，上上狀態是l 。
那麼首先判斷k 和 j的狀態可行性，首先j不能出現在k的上方，那就是(st[j][i - 1] & st[k][i]) ，然後k 也不能出現在j的左下和右下的位置，通過上圖可以看出，k不能出現在j的左移一位，右移一位的位置。那麼可以這麼判斷(st[j][i - 1] >> 1 & st[k][i]), (st[j][i - 1] << 1 & st[k][i]) 。這樣就處理完j 和k 這兩個狀態了。
接下來是j和l，這裡的判斷同j和k，因為都是相鄰的兩行，這裡不多說了，一樣的，下面著重講一下l和k的狀態的判斷。
因為l和k之間是可能隔著X的，所以我們不能直接判斷，而應該判斷他們之間是否有X。
比如判斷l是否在k上方，那麼不能直接(st[l][i - 2] & st[k][i])，因為他們之間如果有X，那麼該狀態是成立的。
那麼到底如何判斷呢。昨天我也是在這裡卡住了，今天早上突然想到，其實我們只要判斷l狀態和k狀態都是1的位置，那麼他們的i - 1行該位置是否是X就行了。而判斷X我們可以直接使用壓縮過的地圖進行判斷。
那麼可以這樣：
int s = (st[l][i - 1] & st[k][i]) ;
if(s & M[i - 1] != s)
那麼就證明他們之間是會互相攻擊的，s & (M[i -1] ) != s，就說明l和k都為1的位置他們中間至少有一處不為X，那麼該狀態不可行。
同理我們可以判斷 l狀態的左下攻擊和右下攻擊是否會打到k狀態。
如果是左下攻擊，那麼只需要將l狀態左移兩位與k判斷，然後判斷他們的之間是否有X。具體看代碼，我就不多解釋了，相信自己動手畫張圖還是很好理解的。
同理右下攻擊。
至於為什麼相鄰兩列之間的左下攻擊右下攻擊不需要判斷X，相信大家想一下都能想到。
下面貼代碼。
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#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<int,int>
#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[3][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[1] ; i ++ ){
if(st[i][1] & M[1])continue ;
for (int j = 0 ; j < num[0] ; j ++ ){
if(st[j][0] & st[i][1])continue ;
if(st[j][0] >> 1 & st[i][1])continue ;
if(st[j][0] << 1 & st[i][1])continue ;
dp[1][j][i] = max(dp[1][j][i] , dp[0][0][j] + Count[i][1]) ;
}
}
//狀態轉移過程
for (int i = 2 ; i < n ; i ++ ) {
for (int j = 0 ; j < num[i - 1] ; j ++ ) {
for (int k = 0 ; k < num[i] ; k ++ ) {
if((M[i] & st[k][i])|| (M[i - 1] & st[j][i - 1]) ||
((st[j][i - 1] << 1) & st[k][i]) || ((st[j][i - 1] >> 1) & st[k][i]))continue ;
if(st[j][i - 1] & st[k][i])continue ;
for (int l = 0 ; l < num[i - 2] ; l ++ ) {
if((M[i - 2] & st[l][i - 2] )|| (st[l][i - 2] & st[j][i - 1])) continue ;
if(((st[l][i - 2] >> 1) & st[j][i - 1]) || ((st[l][i - 2] << 1) & st[j][i - 1]))continue ;
if(!dp[(i + 2) % 3][l][j]) continue ;
int s = (st[l][i - 2] >> 2 ) & st[k][i] ;//右下
if(s) {
s <<= 1 ;
if((s & M[i - 1]) != s)continue ;
}
s = (st[l][i - 2] << 2 ) & st[k][i] ;//左下
if(s) {
s >>= 1 ;
if((s & M[i - 1]) != s)continue ;
}
s = (st[l][i - 2]) & st[k][i] ;//上方
if(s){
if((s & M[i - 1]) != s)continue ;
}
dp[i % 3][j][k] = max(dp[i % 3][j][k] , dp[(i + 2) % 3][l][j] + Count[k][i]) ;
ans = max(ans ,dp[i % 3][j][k]) ;
// bug ;
}
}
}
}
cout << ans << endl ;
}
return 0 ;
}
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#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<int,int>
#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[3][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[1] ; i ++ ){
if(st[i][1] & M[1])continue ;
for (int j = 0 ; j < num[0] ; j ++ ){
if(st[j][0] & st[i][1])continue ;
if(st[j][0] >> 1 & st[i][1])continue ;
if(st[j][0] << 1 & st[i][1])continue ;
dp[1][j][i] = max(dp[1][j][i] , dp[0][0][j] + Count[i][1]) ;
}
}
//狀態轉移過程
for (int i = 2 ; i < n ; i ++ ) {
for (int j = 0 ; j < num[i - 1] ; j ++ ) {
for (int k = 0 ; k < num[i] ; k ++ ) {
if((M[i] & st[k][i])|| (M[i - 1] & st[j][i - 1]) ||
((st[j][i - 1] << 1) & st[k][i]) || ((st[j][i - 1] >> 1) & st[k][i]))continue ;
if(st[j][i - 1] & st[k][i])continue ;
for (int l = 0 ; l < num[i - 2] ; l ++ ) {
if((M[i - 2] & st[l][i - 2] )|| (st[l][i - 2] & st[j][i - 1])) continue ;
if(((st[l][i - 2] >> 1) & st[j][i - 1]) || ((st[l][i - 2] << 1) & st[j][i - 1]))continue ;
if(!dp[(i + 2) % 3][l][j]) continue ;
int s = (st[l][i - 2] >> 2 ) & st[k][i] ;//右下
if(s) {
s <<= 1 ;
if((s & M[i - 1]) != s)continue ;
}
s = (st[l][i - 2] << 2 ) & st[k][i] ;//左下
if(s) {
s >>= 1 ;
if((s & M[i - 1]) != s)continue ;
}
s = (st[l][i - 2]) & st[k][i] ;//上方
if(s){
if((s & M[i - 1]) != s)continue ;
}
dp[i % 3][j][k] = max(dp[i % 3][j][k] , dp[(i + 2) % 3][l][j] + Count[k][i]) ;
ans = max(ans ,dp[i % 3][j][k]) ;
// bug ;
}
}
}
}
cout << ans << endl ;
}
return 0 ;
}
