三进制状压 DP。
用 \(0/1/2\) 表示一个格子下方没有格子 / \(1\) 个格子 / \(2\) 个格子被覆盖，转移时枚举上一行状态，在单行内搜索生成所有合法的下一行状态转移，可过（
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
using namespace std;
const int N = 150;
const int M = 10;
const int S = 59049;
int T,n,m,k,full;
int pw[M + 5];
int a[N + 5][M + 5];
int f[N + 5][S + 5],ans;
int s,pre;
void trans(int i,int j,int v)
{
if(j > m)
{
f[i][s] = max(f[i][s],v);
return ;
}
if(j < m && i + 1 < n && !a[i][j] && !a[i][j + 1] && !(pre / pw[j - 1] % 3) && !(pre / pw[j] % 3))
s += pw[j - 1] + pw[j] << 1,
trans(i,j + 2,v + 1),
s -= pw[j - 1] + pw[j] << 1;
if(j + 1 < m && i < n && !a[i][j] && !a[i][j + 1] && !a[i][j + 2] && !(pre / pw[j - 1] % 3) && !(pre / pw[j] % 3) && !(pre / pw[j + 1] % 3))
s += pw[j - 1] + pw[j] + pw[j + 1],
trans(i,j + 3,v + 1),
s -= pw[j - 1] + pw[j] + pw[j + 1];
trans(i,j + 1,v);
}
int main()
{
pw[0] = 1;
for(register int i = 1;i <= M;++i)
pw[i] = pw[i - 1] * 3;
scanf("%d",&T);
for(;T;--T)
{
memset(a,0,sizeof a),memset(f,-1,sizeof f),ans = 0;
scanf("%d%d%d",&n,&m,&k),full = pw[m] - 1;
for(int x,y;k;--k)
scanf("%d%d",&x,&y),a[x][y] = 1;
f[0][0] = 0;
for(register int i = 1;i <= n;++i)
for(register int j = 0,flag;j <= full;++j)
if(~f[i - 1][j])
{
pre = s = j,flag = 0;
for(register int l = 1;l <= m;++l)
if(s / pw[l - 1] % 3)
{
if(a[i][l])
{
flag = 1;
break;
}
s -= pw[l - 1];
}
!flag && (trans(i,1,f[i - 1][j]),1);
}
for(register int i = 0;i <= full;++i)
ans = max(ans,f[n][i]);
printf("%d\n",ans);
}
}