这是一道 DP 好题，代码实现难度并不大。

看到 $m\leq 10$ 不难想到状压，可惜这里的格子比较复杂，有 $2\times 3$ 和 $3\times 2$ 两种格式。

沿用蓝书上炮兵阵地的方法二的思想，不难想到一个三进制状压的方法。

用 $f(i,j)$ 表示第 $i$ 行状态为 $j$ 时前 $i$ 行的最大填充数。

三进制下表示的数有 $0,1,2$，令 $2$ 下面必须为 $1$，$1$ 下面必须为 $0$，$0$ 下面可以任意填。

那么只需要在 $2\times 3$ 的格子的最上面一行填上两个 $3$，在 $3\times 2$ 的格子上同理填上三个 $2$ 即可。

由于限制条件较多，最好使用 DFS 进行填充（思考状态往哪去，而不是思考状态从哪来）。

时间复杂度 $O(n\times 3^m)$，当然还要乘上 DFS 转移的复杂度.

但可以发现符合条件的状态数很少，所以可以轻松跑过。

还有一点需要注意的是，本题空间较为紧张，需要使用滚动数组优化。

参考代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int T, n, m, k, ans;
int p[15];
int f[2][60000];
bool a[151][11];

int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0' || c>'9') f=(c=='-')?-1:1,c=getchar();
    while(c>='0' && c<='9') x=x*10+c-48,c=getchar();
    return x*f;
}

bool Valid(int state, int l1, int r1, int l2, int r2){
    if(l2 > n || r2 >= m) return false;
    for(int i = r1; i <= r2; i ++)
        if(state / p[i] % 3 != 0) return false;
    for(int i = l1; i <= l2; i ++)
        for(int j = r1; j <= r2; j ++) if(a[i][j]) return false;
    return true;
}

void dfs(int i, int state, int pos, int now, int sum, int last, int num){
    if(pos == m){
        f[i&1][now] = max(f[i&1][now], f[(i - 1)&1][state] + sum);
        ans = max(ans, f[i&1][now]);
        return;
    }
    if((state / p[pos]) % 3 >= 1){
        dfs(i, state, pos + 1, now + p[pos] * ((state / p[pos]) % 3 - 1), sum, last, num);
        return;
    }
    if(pos <= last){
        dfs(i, state, pos + 1, now + p[pos] * num, sum, last, num);
        return;
    }
    if(Valid(state, i, pos, i + 2, pos + 1))
        dfs(i, state, pos + 1, now + p[pos] * 2, sum + 1, pos + 1, 2);
    if(Valid(state, i, pos, i + 1, pos + 2))
        dfs(i, state, pos + 1, now + p[pos] * 1, sum + 1, pos + 2, 1);
    dfs(i, state, pos + 1, now, sum, last, num);
}

int main(){
    T = read();
    while(T --){
        memset(f, -1, sizeof(f));
        memset(a, false, sizeof(a));
        n = read(), m = read(), k = read();
        for(int i=1; i<=k; i++){
            int x = read(), y = read() - 1;
            a[x][y] = true;
        }
        p[0] = 1;
        for(int i=1; i<=m; i++) p[i] = p[i - 1] * 3;
        f[0][0] = 0; ans = 0;
        for(int i=1; i<=n; i++)
            for(int j=0; j<p[m]; j++)
                if(f[(i - 1)&1][j] >= 0){
                    dfs(i, j, 0, 0, 0, -1, 0);
                    f[(i - 1)&1][j] = -1;
                }
        printf("%d\n", ans);
    }
    return 0;
}

完结撒花