吾爱破解 - 52pojie.cn

 找回密码
 注册[Register]

QQ登录

只需一步,快速开始

查看: 472|回复: 0
收起左侧

[学习记录] C++数学题的深搜做法

  [复制链接]
Randle 发表于 2024-11-6 20:49

矩形分割

题目描述

有一个长为 $a$,宽为 $b$ 的矩形($1 \le a \le 6$$2 \le b \le 6$)。可以把这个矩形看作是 $a\times b$ 个小方格。

我们现在接到了这样的一个任务:请你计算出,把这个矩形分割成两个部分的方法总数。

你不是可以任意地分割这个大的矩形,必须满足:

分割后,每个部分,至少各自均有一个方格是在大矩形的最外边上(即大矩形最外面一环的方格)。

输入格式

输入文件仅包含两个数字,$a$$b$

输出格式

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

样例 #1

样例输入 #1

3 2

样例输出 #1

15

提示


上述是题目



我的做法:
1、
[C++] 纯文本查看 复制代码
#include<iostream>
using namespace std;
int a[30]={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[m-2];
	}else if(n==2){
		cout<<a[m+3];
	}else if(n==3){
		cout<<a[m+8];
	}else if(n==4){
		cout<<a[m+13];
	}else if(n==5){
		cout<<a[m+18];
	}else if(n==6){
		cout<<a[m+23];
	}
}

数学打表

2、
[C++] 纯文本查看 复制代码
#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;
    }


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



其实搜索很好实现,有什么建议请在下方提出,谢谢

免费评分

参与人数 3吾爱币 +3 热心值 +3 收起 理由
DayBreak + 1 + 1 我很赞同!
士道卄亓 + 1 + 1 用心讨论,共获提升!
wari01 + 1 + 1 用心讨论,共获提升!

查看全部评分

发帖前要善用论坛搜索功能,那里可能会有你要找的答案或者已经有人发布过相同内容了,请勿重复发帖。

您需要登录后才可以回帖 登录 | 注册[Register]

本版积分规则

返回列表

RSS订阅|小黑屋|处罚记录|联系我们|吾爱破解 - LCG - LSG ( 京ICP备16042023号 | 京公网安备 11010502030087号 )

GMT+8, 2024-11-24 11:53

Powered by Discuz!

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表