HDU1185

hdu1185.cpp

#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#define MEM(a,b) memset(a, b, sizeof(a))
using namespace std;

const int N = 105;
const int M = 15;

int n, m;
char buf[12];
int qmap[N];
int dp[N][64][64];
vector<int> valids;

int cnt(int st) {
    int ret = 0;
    while (st) {
        if (st & 1) ret++;
        st >>= 1;
    }
    return ret;
}

int main() {
    MEM(dp, 0);
    MEM(qmap, 0);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%s", buf);
        for (int j = 0; j < m; j++) {
            if (buf[j] == 'P') qmap[i] += (1 << (m - 1 - j));
        }
    }
    for (int st = 0; st < (1 << m); st++) {
        if ((st & (st >> 1)) == 0 &&
                (st & (st >> 2)) == 0)
            valids.push_back(st);
    }
    int ans = 0;
    for (int i = 0; i < valids.size(); i++) {
        if ((valids[i] & qmap[1]) == valids[i]) {
            dp[1][i][0] = cnt(valids[i]);
            ans = max(ans, dp[1][i][0]);
        }
    }

    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < valids.size(); j++) {
            if (!((valids[j] & qmap[i]) == valids[j])) continue;
            for (int k = 0; k < valids.size(); k++) {
                if (!((valids[k] & qmap[i - 1]) == valids[k])) continue;
                for (int l = 0; l < valids.size(); l++) {
                    if (!((valids[l] & qmap[i - 2]) == valids[l])) continue;
                    if ((valids[j] & valids[k]) == 0 &&
                            (valids[j] & valids[l]) == 0 &&
                            (valids[k] & valids[l]) == 0) {
                        dp[i][j][k] = max(dp[i][j][k], dp[i - 1][k][l] + cnt(valids[j]));
                        ans = max(ans, dp[i][j][k]);
                    }
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}