Blog gardens are better

Topic description

Given an N * M matrix, some of which cannot be used, ask how many 2 * 3 rectangles can be placed in this matrix. Can be horizontal or vertical.

For data of \ (100 \% \), \ (1 \leq D \leq 5\), \ (1 \leq N \leq 150\), \ (1 \leq M \leq 10\), \ (0 \leq K \leq M × N\), \(1 \leq x \leq N\), \(1 \leq y \leq M\) .

topic analysis

Thought analysis

My first reaction when I saw this question was Mondrian's dream , very similar, but the rectangle size for this question is not the same.

One way of doing that question is to press DP in a state. In each line of state binary, 1 represents the upper half of a domino (that is, the domino must be placed vertically), and 0 represents other situations. The final answer is f[n][0] .

Looking at the data range of this question again, M is very small, and it is almost inseparable from the DP. Following the above practice, it will be found that due to the size of the rectangle, pure binary does not seem to meet all requirements.

Only 2 lines can be represented when placed horizontally, but 3 lines when placed vertically. That naturally comes to mind in base 3.

It can be expressed like this:

Then you can enumerate each row, consider enumerating all eligible states of this row from the feasible state of the previous row, and then update.

enum state details

1. If the current position of the previous line has a value, but this point cannot be used, return directly.
2. 0 if the current point is not available.
3. If the current position of the previous row is non-zero, the value -1 of the previous row.
4. If the position in the previous line, that is, the next two positions are both zero, and these points in this line are available, they can be set to 1 together.
5. If the position in the previous line, that is, the position after it, is zero, and these points in this line are available, they can be set to 2 together.
6. This position is 0 .

Meet the first three first, if it is one of the first three, dfs returns directly after completion.

Otherwise, there are three remaining cases after enumeration. See the code for details.

Because the spatial extent is small, scroll the array a bit.

Code

#include<bits/stdc++.h>
//By _yolanda_
using namespace std;
#define int long long

const int N=6e4+5,INF=1e15;
int f[2][N],w[200][20];
int n,m;
int in[15];

inline int read(){
	int sum=0,f=1;char a=getchar();
	while(a<'0' || a>'9'){if(a=='-') 	f=-1;a=getchar();}
	while(a>='0' && a<='9') 	sum=sum*10+a-'0',a=getchar();
	return sum*f;
}

inline int get(int x,int y){ //Find the y th digit of x in base 3
	int tmp=in[y];
	return (x/tmp)%3;
}
void dfs(int x,int y,int no,int pre,int sum){
	if(y==m){//to the border, update
		f[x%2][no]=max(f[(x%2)^1][pre]+sum,f[x%2][no]);
		return;
	}
	int t=get(pre,m-y-1); //On the previous line, the value of this position
	if(w[x][y+1]){ //This location cannot be used
		if(t)	return;
		dfs(x,y+1,no*3,pre,sum);
	}
	else if(t){
		dfs(x,y+1,no*3+t-1,pre,sum);//Case 3
	}
	else{
		if(x<n && m-y>=3 && !get(pre,m-y-2) && !get(pre,m-y-3) && !w[x][y+2] && !w[x][y+3]){
			int tmp=no*3+1;tmp=tmp*3+1,tmp=tmp*3+1;
			dfs(x,y+3,tmp,pre,sum+1);
		}//Fill in 3 1s in a row
		if(x<n-1 && m-y>=2 && !get(pre,m-y-2) &&!w[x][y+2]){
			int tmp=no*3+2;tmp=tmp*3+2;
			dfs(x,y+2,tmp,pre,sum+1);
		}//Fill in 3 2 in a row
		dfs(x,y+1,no*3,pre,sum);//Fill in 0
	}
}

signed main(){
	
	in[0]=1;
	for(int i=1;i<=10;++i)	in[i]=in[i-1]*3;
	int T,k;T=read();
	while(T--){
		memset(w,0,sizeof w);
		memset(f,0,sizeof f);
		n=read(),m=read(),k=read();
		
		int tp=pow(3,m);
		int xx,yy;
		for(int i=1;i<=k;++i){
			xx=read(),yy=read();
			w[xx][yy]=1;
		}
		dfs(1,0,0,0,0);
		for(int i=2;i<=n;++i){
			for(int j=0;j<tp;++j)	f[i%2][j]=-INF;
			for(int j=0;j<tp;++j)
				if(f[(i-1)%2][j]>=0)	dfs(i,0,0,j,0);
				//The state of the previous line can only be updated when it is available, otherwise it will be TLE
		}
		printf("%lld\n",f[n%2][0]);
	}
	
	return 0;
}