C++数学题的深搜做法
# 矩形分割## 题目描述
有一个长为 $a$，宽为 $b$ 的矩形（$1 \le a \le 6$，$2 \le b \le 6$）。可以把这个矩形看作是 $a\times b$ 个小方格。
我们现在接到了这样的一个任务：请你计算出，把这个矩形分割成两个部分的方法总数。
你不是可以任意地分割这个大的矩形，必须满足：
分割后，每个部分，至少各自均有一个方格是在大矩形的最外边上（即大矩形最外面一环的方格）。
## 输入格式
输入文件仅包含两个数字，$a$ 和 $b$。
## 输出格式
输出仅有一行一个整数，表示分割的方案总数。
## 样例 #1
### 样例输入 #1
```
3 2
```
### 样例输出 #1
```
15
```
## 提示
上述是题目
我的做法：
1、
#include<iostream>
using namespace std;
int a={1,2,3,4,5,6,15,28,45,66,15,52,143,350,799,28,143,614,2431,9184,45,350,2431,16000,102147,66,799,9184,102147,1114394};
int main()
{
int n;int m;
cin>>n>>m;
if(n==1){
cout<<a;
}else if(n==2){
cout<<a;
}else if(n==3){
cout<<a;
}else if(n==4){
cout<<a;
}else if(n==5){
cout<<a;
}else if(n==6){
cout<<a;
}
}
数学打表
2、
#include<bits/stdc++.h>
using namespace std;
#define N 10
int n,m;
int ans=0;
int movex={1,0,-1,0};
int movey={0,1,0,-1};
int vis;
void dfs(int x,int y)
{
vis=1;
if(x==1 || y==m || x==n || y==1) //到达另一个边缘点
{
ans++;
vis=0;
return;
}
for(int i=0;i<4;++i)
{
int xx=x+movex,yy=y+movey;
if(xx<1 || yy<1 || xx>n || yy>m || vis) continue;
dfs(xx,yy);
}
vis=0;
}
int main()
{
scanf("%d%d",&n,&m);
n++;m++; //转换为点图
memset(vis,0,sizeof(vis));
for(int i=2;i<n;++i) //这么写就是为了去掉交点
{
vis=1;//手动将出发点设为已访问
dfs(i,2);//然后手动走第一步，防止无效切割
vis=0;//回溯
}
for(int i=2;i<m;++i) //同上
{
vis=1;
dfs(2,i);
vis=0;
}
printf("%d",ans);
return 0;
}
这道题的思路实际非常简单
一个由ab个小矩形组成的矩形
事实上可以看成一个由(a+1)(b+1)个点组成的点图
那么题目就可以转换为从一个边缘上的点出发，到另一个边缘点，一共有几个方案
为了避免重复方案的出现，我们将出发点设置在最左及最上的边上（或者最右和最下的边）
接下来考虑无效切割的处理（如切割(1,1)与(2,1)之间的边，这样图依然只有一个），显然，如果我们直接从边缘点开始搜索，无效切割的出现是必然的，所以我们需要做一些处理
首先，不将矩形的四个顶点（即边与边的交点）作为出发点，因为从顶点出发必然会导致无效切割
其次，我们手动将出发点走到点阵内(如从(1,1)到(1,2)),然后再进行搜索，就可以避免无效切割。这时可能会有人问，如果"手动走到的那个点"也是边缘点怎么办？我们只需要把关于边缘点的判断写在dfs开头即可。
最后，跳出搜索的条件就是当前位置再次到达边缘点，答案+1，回溯
其实搜索很好实现，有什么建议请在下方提出，谢谢
页:
[1]