状态压缩一下当前各格子以及上面总共放了几块，只有012三种情况，直接三进制保存即可。
然后转移的时候用搜索找出所有的状态进行转移。
#include <map>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
#define ll long long
#define mp make_pair
#define mask(i) ((mask%pow[i+1])/pow[i])
#define a(i) (a[x][i])
int dp[2][500005],pow[20],n,m,k;
int a[205][20],t,now,pre;
void print(int mask)
{F(i,0,m-1)printf("%d",(mask%pow[i+1])/pow[i]);}
void dfs(int x,int y,int mask,int val)
{
// printf("Dfs %d %d %d ",x,y,val); print(mask); printf("\n");getchar();
if (y>=m){dp[pre][mask]=max(val,dp[pre][mask]);return;}
if (y+2<m&&!a(y)&&!a(y+1)&&!a(y+2)&&mask(y)==mask(y+1)&&mask(y+1)==mask(y+2))
{
if (mask(y)==1)
{
// print(mask); printf(" to ");
mask-=pow[y]+pow[y+1]+pow[y+2];
// print(mask); printf("\n");
dfs(x,y+3,mask,val+1);
mask+=pow[y]+pow[y+1]+pow[y+2];
}
else
{
// print(mask); printf(" to ");
mask+=pow[y]+pow[y+1]+pow[y+2];
// print(mask); printf("\n");
dfs(x,y+3,mask,val);
mask-=pow[y]+pow[y+1]+pow[y+2];
}
}
if (y+1<m&&!a(y)&&!a(y+1)&&mask(y)==mask(y+1))
{
if (mask(y)<2)
{
// print(mask); printf(" to ");
mask+=pow[y]+pow[y+1];
// print(mask); printf("\n");
dfs(x,y+2,mask,val);
mask-=pow[y]+pow[y+1];
}
else
{
// print(mask); printf(" to ");
mask-=2*pow[y]+2*pow[y+1];
// print(mask); printf("\n");
dfs(x,y+2,mask,val+1);
mask+=2*pow[y]+2*pow[y+1];
}
}
// printf("%d mask (%d)\n",mask(y),y);
if (!mask(y))
{
dfs(x,y+1,mask,val);
}
}
int main()
{
scanf("%d",&t);
pow[0]=1;
F(i,1,14)pow[i]=pow[i-1]*3;
while (t--)
{
memset(a,0,sizeof a);
scanf("%d%d%d",&n,&m,&k);
F(i,1,k)
{
int x,y;scanf("%d%d",&x,&y);
x--; y--;
a[x][y]=1;
}
F(i,0,m-1) a[n][i]=1;
now=1;pre=0;
memset(dp[pre],-1,sizeof dp[pre]);
dp[pre][0]=0;
F(i,0,n)
{
now^=1; pre^=1;
memset(dp[pre],-1,sizeof dp[pre]); //printf("memset %d\n",pre);
F(j,0,pow[m]-1) if (~dp[now][j])
{
// printf("%d is no ",i); print(j); printf(" == ");printf("%d\n",dp[now][j]);
dfs(i,0,j,dp[now][j]);
}
}
printf("%d\n",dp[pre][0]);
}
}