P4537 [CQOI2007]矩形

巧妙的计数题。

考虑爆搜不与边界重合的分界线，显然，任意一种方案都有其独一无二的分界线，并且任意一条分界线只会在起点和终点处被各搜到一次。

分三种情况讨论（不考虑方向）：

• 左侧或上侧边界至右侧或下侧边界。
• 左侧边界至上侧边界或右侧边界至下测边界。
• 起点和终点位于同一边界。

对于第一种情况，只算左侧边界和上测边界即可；对于后两种情况，容易发现内部是对称的，如果每个边界都算，会算重一倍，那我们只算左侧边界和上侧边界就恰好填补了。

所以三种情况的计算就统一了。

接着来看下具体怎么搜，可行的路径并是 \((n-1)\times(m-1)\) 的矩形，其中四个边界都向外伸出一条边。

起点和终点必然是伸出去的边，那么只需要以矩形左侧边界 \(n\) 个点和上侧边界 \(m\) 个点各搜一遍。注意 \((1,1)\) 要算两次因为它伸出了两条边。

特判 \(n=1\) 的情况。

接着来看常数优化。

继续利用矩形的对称性，每个边界只需搜一半就好了，另一半答案对称。

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 4
#define Max(x,y)((x)>(y)?x:y)
#define For(i,x,y)for(i=x;i<=(y);i++)
const int dx[N]={-1,0,1,0},dy[N]={0,-1,0,1};
ll s;
int n,m;
bool vis[7][8];
void dfs(int x,int y)
{
	if(!x||x==n||!y||y==m)s++;
	else
	{
		int i,dl,dr;
		vis[x][y]=1;
		For(i,0,3)
		{
			dl=x+dx[i];
			dr=y+dy[i];
			if(!vis[dl][dr])dfs(dl,dr);
		}
		vis[x][y]=0;
	}
}
int main()
{
	int i;
	ll t=0;
	cin>>n>>m;
	if(n==1)cout<<Max(n,m)-1,exit(0);
	For(i,1,(n-1)>>1)
	{
		dfs(i,1);
		t+=(s-1)<<1;
		s=0;
	}
	For(i,1,(m-1)>>1)
	{
		dfs(1,i);
		t+=(s-1)<<1;
		s=0;
	}
	if(!(n&1))
	{
		dfs(n>>1,1);
		t+=s-1;
		s=0;
	}
	if(!(m&1))dfs(1,m>>1),t+=s-1;
	cout<<t;
	return 0;
}

P4537 [CQOI2007]矩形

原文：https://www.cnblogs.com/May-2nd/p/14904963.html