10257번: Stains

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

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
int t, m, n, c, st[1001][10], dp[1001][60000];
vector<int> cd;
int f(int h, int b) {
    if (h > n) return 0;
    int &ret = dp[h][b];
    if (~ret) return ret;
    int ck[10] = {};
    ret = 1e9;
    for (int &it : cd) {
        int cnt = 0, flag = 0, nxt = 0;
        for (int i = b, j = 0; j < m; i /= 3, j++) ck[j] = i % 3;
        for (int i = 0; i < m - 2; i++) if (1 << i&it) {
            cnt++;
            for (int j = i; j < i + 3; j++) ck[j] = 3;
        }
        for (int i = m; i--;) {
            if (st[h][i] && !ck[i]) flag = 1;
            if (ck[i]) ck[i]--;
            nxt = nxt * 3 + ck[i];
        }
        if (!flag) ret = min(ret, cnt + f(h + 1, nxt));
    }
    return ret;
}
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d%d%d", &m, &n, &c);
        cd.clear();
        memset(dp, -1, sizeof(dp));
        memset(st, 0, sizeof(st));
        for (int i = 1 << m - 2; i--;) {
            int flag = 0;
            for (int j = 1; j < m - 3; j++) if (1 << j & i && 1 << j - 1 & i) flag = 1;
            for (int j = 2; j < m - 3; j++) if (1 << j & i && 1 << j - 2 & i) flag = 1;
            if (flag) continue;
            cd.push_back(i);
        }
        for (int i = 0, x, y; i < c; i++) {
            scanf("%d%d", &x, &y);
            st[y][x - 1] = 1;
        }
        printf("%d\n", f(1, 0));
    }
    return 0;
}