# Poj Solution 1038

```http://poj.org/problem?id=1038

//* @author
import java.util.*;

public class Main {
static Scanner in = new Scanner(System.in);
static int[] p = new int[12];
static {
p[0] = 1;
for(int i=1; i!=p.length; ++i)
p[i] = 3*p[i-1];
}

static int get(int s, int i) {
return s/p[i]%3;
}

static int set(int s, int i, int v) {
return s+(v-get(s, i))*p[i];
}

public static void main(String[] args) {
int t = in.nextInt();
while(t-->0) {
int n = in.nextInt();
int m = in.nextInt();
if(m>10) while(true);
boolean[][] map = new boolean[n+1][m+1];
for(int i=0; i<=n; ++i) map[i][m] = true;
for(int j=0; j<=m; ++j) map[n][j] = true;
int k = in.nextInt();
while(k-->0) map[in.nextInt()-1][in.nextInt()-1] = true;
int[][] dp = new int[m+1][p[m]];
dp[0][p[m]-1]=1;
for(int i=0; i!=n; ++i) {
for(int j=0; j!=m; ++j) {
for(int s=0, _s; s!=p[m]; ++s) {
int x = dp[j][s];
if(x==0)continue;
int l = get(s, j);
_s = set(s, j, Math.min(2, l+1));
dp[j+1][_s] = Math.max(dp[j+1][_s], x);
int r = get(s, j+1);
if(l!=2||r!=2) continue;
if(map[i+0][j+0]) continue;
if(map[i+0][j+1]) continue;
if(map[i+1][j+0]) continue;
if(map[i+1][j+1]) continue;
if(!map[i+2][j]&&!map[i+2][j+1]) {
_s = set(set(s, j, 0), j+1, 0);
if(j+2>m)while(true);
dp[j+2][_s] = Math.max(dp[j+2][_s], x+1);
}
if(get(s, j+2)==2&&!map[i][j+2]&&!map[i+1][j+2]) {
_s = set(set(set(s, j, 1), j+1, 1), j+2, 1);
if(j+3>m)while(true);
dp[j+3][_s] = Math.max(dp[j+3][_s], x+1);
}
}
}
int[] tmp = dp[m];
for(int j=m; j>=1; --j)
Arrays.fill(dp[j] = dp[j-1], 0);
dp[0] = tmp;
}
int ans = 0;
for(int s=0; s!=p[m]; ++s)
ans = Math.max(ans, dp[0][s]);
System.out.println(ans-1);
}
}
}

```
This entry was posted in poj. Bookmark the permalink.