题解 | #[CQOI2007]矩形RECT#

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<set>
#include<unordered_map>
using namespace std;

inline long long  read() {
	long long x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-')f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}
inline void ou(long long  x) {
	char ch[40];
	int len = 0;
	if (x < 0) {
		putchar('-');
		x = ~x + 1;
	}
	do {
		ch[len++] = x % 10 + '0';
		x /= 10;
	} while (x > 0);
	for (int i = len - 1; i >= 0; i--) putchar(ch[i]);
	return;
}
int N, M;
bool vis[7][8];
int dr[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
int ans = 0;
void dfs(int x, int y) {
	if (x == 0 || x == N || y == 0 || y == M) { //分割线的一个端点到边界
		ans++;
		return ;
	} 
	int t_x,t_y;
	vis[x][y]=1;
		for (int i = 0; i < 4; i++) {
			t_x=x + dr[i][0];
			t_y=y + dr[i][1];
			if (vis[t_x][t_y]) //分割线另外一个端点的移动
				continue;
				
			vis[t_x][t_y] = true;
			dfs(t_x,t_y); //分割线继续移动
			vis[t_x][t_y] = false; //回溯
		}
	
	return ;
}


int main() {
	cin >> N >> M;
	ans=0;
	for (int i = 1; i < N; i++) {
        //删去上一条分割线
		memset(vis, false, sizeof(vis));
        //创建新分割线
		vis[i][0] = true; //分割线的一个端点
		dfs(i, 1);
	}
    //由于图案的对称性,会出现相同的分割线,我们认为其中一个是镜像分割线
    //在计算过程图一会出现两次,我们认为出现了图一和图二
	for (int i = 1; i < M; i++) {
		memset(vis, false, sizeof(vis));
		vis[0][i] = true;
		dfs(1, i);
	}
	cout << ans;
	return 0;
}