1014번: 컨닝

https://www.acmicpc.net/problem/1014

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, r, t;
char s[11][11];
bool f(int x, int y) {
    int i = 0;
    for (; i < m; i++)
        if (s[x][i] == 'x' && 1 << i & y || i && 1 << i&y && 1 << i - 1 & y) return false;
    return true;
}
int main() {
    for (scanf("%d", &t); t--;) {
        int dp[11][1 << 10] = { 0, };
        r = 0;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            scanf("%s", s + i);
            for (int j = 1 << m; --j >= 0;) {
                if (!f(i, j)) continue;
                int bt = 0;
                for (int k = 0; k < m; k++) if (1 << k&j) {
                    if (k) bt |= 1 << k - 1;
                    if (k < m - 1) bt |= 1 << k + 1;
                }
                for (int k = 1 << m; --k >= 0;) {
                    if (bt & k || !f(i - 1, k)) continue;
                    dp[i][j] = max(dp[i][j], dp[i - 1][k]);
                }
                for (int k = j; k; k &= k - 1) dp[i][j]++;
                r = max(r, dp[i][j]);
            }
        }
        printf("%d\n", r);
    }
    return 0;
}