一道状压好题。
总体向下,局部向右,对于每一个位置,记录前两个位置,前一个位置、当前位置是否不可用,如果都可用,记为$0$,第一个位置不可用,记为$1$,如果当前位置不可用,记为$2$。之后试着竖着填或者横着填。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define gc getchar()
using namespace std;
const int N=156,M=16;
 
inline void qr(int &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int n,m,k,f[2][60000],prv[M],cur[M];bool v[N][M];
/*prv,cur的值所表达的意义是一样的,cur[j]=2表示当前这一行第j个数已经被占用也就是v[i][j]=1,prv则表示v[i-1][j]=1,
=1时,cur->v[i-1][j]=1,prv->v[i-2][j]=1,否则=0,没有被占用。*/
int p[]={1,3,9,27,81,243,729,2187,6561,19683,59049};
inline int calc10(int *a)
{
    int ans=0;
    for(int i=0;i<m;i++)ans+=a[i]*p[i];
    return ans;
}
inline void calc3(int x,int *a)
{
    for(int i=0;i<m;i++)
        a[i]=x%3,x/=3;
}
void dfs(int now,int j,int last,int state)//向下移动 ,state表示当前状态 
{
    f[now][state]=max(f[now][state],last);
    if(j>=m)return ;
    if(j+1<m&&!prv[j]&&!prv[j+1]&&!cur[j]&&!cur[j+1])//试着填一个横着的 
    {
        cur[j]=cur[j+1]=2;
        dfs(now,j+2,last+1,calc10(cur));
        cur[j]=cur[j+1]=0;//回溯 
    }
    if(j+2<m&&!cur[j]&&!cur[j+1]&&!cur[j+2])//竖着填 
    {
        cur[j]=cur[j+1]=cur[j+2]=2;
        dfs(now,j+3,last+1,calc10(cur));
        cur[j]=cur[j+1]=cur[j+2]=0;
    }
    dfs(now,j+1,last,state);//不进行操作。    
}
int main()
{
    int T;qr(T);
    while(T--)
    {
        qr(n),qr(m),qr(k);
        memset(v,0,sizeof(v));
        for(int i=1,x,y;i<=k;i++)
        {
            qr(x),qr(y);v[x][y-1]=1;
        }
        memset(f[0],-1,sizeof(f[0]));
        for(int i=0;i<m;i++)
            prv[i]=v[1][i]?2:1;
        int now=0,tmp=calc10(prv);
        f[now][tmp]=0;
        for(int i=2;i<=n;i++)
        {
            now^=1;
            memset(f[now],-1,sizeof(f[now]));
            for(int j=0;j<p[m];j++)if(f[now^1][j]!=-1)//f[i-1][j]
            {
                calc3(j,prv);//上一层状态为j,把它转化成三进制。 
                for(int k=0;k<m;k++)
                    if(v[i][k])cur[k]=2;
                    else cur[k]=prv[k]?prv[k]-1:0;
                tmp=calc10(cur);//f[i][tmp];
                dfs(now,0,f[now^1][j],tmp);
            }
        }
        int ans=0;
        for(int i=0;i<p[m];i++)ans=max(ans,f[now][i]);
        qw(ans);puts("");
    }
    return 0;
}