ZOJ 3723 (浙大月赛)状压DP (二)
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 ;
}