Jogo do Preto e Branco

#include <bits/stdc++.h>
using namespace std;

int n, m, p;
int black[8][8];
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

// 1 -> white

bool check(int i, int j, int mask1, int mask2) {
    if(black[i][j]) {
        if(mask2 & (1 << j)) return false;
        return true;
    } else {
        if(mask2 & (1 << j)) { // coloquei uma peça branca
            if(i > 0 and (mask1 & (1 << j))) // cima tbm é branco
                return false;
            if(j > 0 and (mask2 & (1 << (j - 1)))) // esq tbm é branco
                return false;
            if(i < m and (mask2 & (1 << (j + 1)))) // dir tbm é branco
                return false;
            int cnt_black = 0;
            for(int k = 0; k < 4; k++) {
                int x = dx[k] + i, y = dy[k] + j;
                if(x >= 0 and x < n and y >= 0 and y < m)
                    cnt_black += black[x][y];
            }
            if(cnt_black == 0) return false;
        }
        return true;
    }
}

int count(int mask) {
    int sz = 0;
    while(mask) {
        sz++;
        mask -= mask&-mask;
    }
    return sz;
}


int dp[7][1 << 7];
int seen[7][1 << 7];

int solve(int i, int mask1) {
    if(i == n) return 0;
    if(seen[i][mask1]) return dp[i][mask1];
    int ans = 0;
    for(int mask2 = 0; mask2 < (1 << m); mask2++) {
        bool ok = true;
        for(int j = 0; j < m; j++)
            if(!check(i, j, mask1, mask2))
                ok = false;
        if(ok) ans = max(ans, solve(i + 1, mask2) + count(mask2));
    }
    seen[i][mask1] = 1;
    return dp[i][mask1] = ans;
}

int32_t main() {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> p;

    for(int i = 0; i < p; i++) {
        int x, y;
        cin >> x >> y;
        black[x - 1][y - 1] = 1;
    }

    cout << solve(0, 0) << endl;

    return 0;
}