矩形分割

1.题目描述

有一个长为 $a$，宽为 $b$ 的矩形（$1 \le a \le 6$，$2 \le b \le 6$）。可以把这个矩形看作是 $a\times b$ 个小方格。 我们现在接到了这样的一个任务：请你计算出，把这个矩形分割成两个部分的方法总数。 你不是可以任意地分割这个大的矩形，必须满足： 分割后，每个部分，至少各自均有一个方格是在大矩形的最外边上（即大矩形最外面一环的方格）。

输入格式

输入文件仅包含两个数字，$a$ 和 $b$。

输出格式

输出仅有一行一个整数，表示分割的方案总数。

样例 #1

样例输入 #1

3 2

样例输出 #1

15

提示

2.分析

2.1 思路

1. 一个由ab个小矩形组成的矩形
2. 事实上可以看成一个由(a+1)(b+1)个点组成的点图
3. 那么题目就可以转换为从一个边缘上的点出发，到另一个边缘点，一共有几个方案
4. 为了避免重复方案的出现，我们将出发点设置在最左及5. 最上的边上（或者最右和最下的边）
5. 接下来考虑无效切割的处理（如切割(1,1)与(2,1)之间的边，这样图依然只有一个），显然，如果我们直接从边缘点开始搜索，无效切割的出现是必然的，所以我们需要做一些处理
6. 首先，不将矩形的四个顶点（即边与边的交点）作为出发点，因为从顶点出发必然会导致无效切割
7. 其次，我们手动将出发点走到点阵内(如从(1,1)到(1,2)),然后再进行搜索，就可以避免无效切割。这时可能会有人问，如果"手动走到的那个点"也是边缘点怎么办？我们只需要把关于边缘点的判断写在dfs开头即可。
8. 最后，跳出搜索的条件就是当前位置再次到达边缘点，答案+1，回溯

2.2 算法步骤

1. 输入处理：读取输入的两个数字 n和 m，表示矩形的长和宽。
2. 转换为点图：将矩形转换为 (n+1) x (m+1) 的点图。
3. 初始化：
   • 初始化一个二维数组 vis用于记录访问状态。
   • 初始化计数器 ans用于记录分割方案的总数。
   • 定义四个方向的移动数组 movex 和 movey。
4. 定义DFS函数：
   • 标记当前点为已访问。
   • 如果当前点是边缘点，则计数器加一，回溯。
   • 遍历四个方向，移动到下一个点，递归调用DFS函数。
   • 回溯时标记当前点为未访问。
5. 遍历所有可能的出发点：
   • 遍历所有可能的出发点，手动将出发点设为已访问，然后手动走第一步，防止无效切割。
   • 调用DFS函数进行搜索。
   • 回溯时将出发点设为未访问。
6. 输出结果：输出计数器的值。

3.代码

#include<bits/stdc++.h>
using namespace std;
#define N 10
int n,m;
int ans=0;
int movex[4]={1,0,-1,0};
int movey[4]={0,1,0,-1};
int vis[N][N];
void dfs(int x,int y)
    {
        vis[x][y]=1;
        if(x==1 || y==m || x==n || y==1) //到达另一个边缘点
            {
                ans++;
                vis[x][y]=0;
                return;
            }
        for(int i=0;i<4;++i)
            {
                int xx=x+movex[i],yy=y+movey[i];
                if(xx<1 || yy<1 || xx>n || yy>m || vis[xx][yy]) continue;
                dfs(xx,yy);
            }
        vis[x][y]=0;
    }
int main()  
    {
        scanf("%d%d",&n,&m);
        n++;m++; //转换为点图
        memset(vis,0,sizeof(vis));
        for(int i=2;i<n;++i) //这么写就是为了去掉交点
            {
                vis[i][1]=1;//手动将出发点设为已访问
                dfs(i,2);//然后手动走第一步，防止无效切割
                vis[i][1]=0;//回溯
            }
        for(int i=2;i<m;++i) //同上
            {
                vis[1][i]=1;
                dfs(2,i);
                vis[1][i]=0;
            }
        printf("%d",ans);
        return 0;
    }