刷题记录:牛客NC19910[CQOI2007]矩形RECT

传送门;牛客

题目描述:

给一个a*b矩形，由a*b个单位正方形组成。你需要沿着网格线把它分成分空的两部分，每部分所有格子连通，且至少
有一个格子在原矩形的边界上。“连通”是指任两个格子都可以通过水平或者竖直路径连在一起。 求方案总数。例如3*2
的矩形有15种方案。
输入:
3 3
输出:
3 3

emmm,一道四星题,洛谷上评级为蓝,但是对于这道题,我们其实是可以进行爆搜的(或者打表),虽然它耳朵正解应该是插头DP,但是插头DP我现在根本不会QAQ,这道题的升级版,这道升级版爆搜就过不去了

主要思路:

1. 我们发现分成两部分可以等价于找到一条路线,这条路线是从一个边界通向另一个边界,假设我们找到了这样的一条边界的话,显然就意味着我们找到了一个可行的方案
2. 对于如何找到这样的一个路线,我们可以采用爆搜的方法,我们先选中边界上的一个点,然后开始搜索,假设我们搜到了除这个点的任何一个边界,就意味着我们找到了一个可行的路线,然后不断的累加即可
3. 对于我们的上述方案,其实我们还是可以进行一个优化的,因为我们的矩形显然是对称的,也就是说我们其实只要算出一半的ans即可

下面是具体的代码部分:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int n,m;
int vis[100][100];
int ans=0;
int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};
void dfs(int x,int y) {
	if(x==0||y==0||x==n||y==m) {//搜索到边界就累加
		ans++;
		return ;
	}
	for(int i=0;i<=3;i++) {
		int xx=x+dx[i],yy=y+dy[i];
		if(vis[xx][yy]==1) continue;
		vis[xx][yy]=1;
		dfs(xx,yy);//继续搜
		vis[xx][yy]=0;//回溯
	}
	return ;
}
int main() {
	n=read();m=read();
	for(int i=1;i+i<n;i++) {
		vis[i][0]=1;vis[i][1]=1;
		dfs(i,1);
		vis[i][0]=0;vis[i][1]=0;
	}
	for(int j=1;j+j<m;j++) {
		vis[0][j]=1;vis[1][j]=1;
		dfs(1,j);
		vis[0][j]=0;vis[1][j]=0;
	}
	//因为是一半,所以答案需要乘2
	ans<<=1;int i,j;
	//一个小优化,因为矩形的对称性,其实不优化这道题也是能够过的
	//但是我们可能中间那一行或者列在之前并没有判断过,所以我们需要特判一下
	if(!(n&1)) i=n>>1,vis[i][0]=1,vis[i][1]=1,dfs(i,1),vis[i][0]=0,vis[i][1]=0;
	if(!(m&1)) j=m>>1,vis[0][j]=1,vis[1][j]=1,dfs(1,j),vis[0][j]=0,vis[1][j]=0;
	cout<<ans<<endl;
	return 0;
}