当前位置:网站首页>[depth first search] Ji suanke: Square
[depth first search] Ji suanke: Square
2022-07-06 18:46:00 【muse_ age】
Suppose the sides of the square are a ,b,c ,d, Each stick Yes 4 A choice : You can join abcd Any one , You can use dfs
dfs(int index,int a,int b,int c,int d)// Enumerate to index And the current side length is abcd
To make a choice
dfs(index+1,a+p[index],b,c,d;// Join in a
dfs(index+1,a,b+p[index],c,d);// Join in b
dfs(index+1,a,b,c+p[index],d);// Join in c
dfs(index+1,a,b,c,d+p[index]);// Join in d
exit :
index==n: Reach the empty node in the search tree , Judge abcd Whether the side lengths are equal
prune :
When side length > Chief, /4 when , It is impossible to form a square , There is no need to search , cut off
Code :
#include<iostream>
using namespace std;
int n;
int p[1000];
int sum=0;
bool flag=false;
void dfs(int index,int a,int b,int c,int d){
if(flag){
return;
}
if(index==n){
if(a==b&&b==c&&c==d&&d==sum/4){
cout<<"YES";
flag=true;
return;
}
}
if(a>sum/4||b>sum/4||c>sum/4||d>sum/4){
return;
}
dfs(index+1,a+p[index],b,c,d);
dfs(index+1,a,b+p[index],c,d);
dfs(index+1,a,b,c+p[index],d);
dfs(index+1,a,b,c,d+p[index]);
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>p[i];
sum+=p[i];
}
if(sum%4!=0){
cout<<"NO";
return 0;
}
else{
dfs(0,0,0,0,0);
}
return 0;
}
边栏推荐
- Breadth first traversal of graph
- POJ 2208 six lengths of tetrahedron are known, and the volume is calculated
- Test 1234
- 当保存参数使用结构体时必备的开发技巧方式
- Crawling data encounters single point login problem
- C#/VB. Net to add text / image watermarks to PDF documents
- RedisSystemException:WRONGTYPE Operation against a key holding the wrong kind of value
- 【中山大学】考研初试复试资料分享
- 基于ppg和fft神经网络的光学血压估计【翻译】
- 用友OA漏洞学习——NCFindWeb 目录遍历漏洞
猜你喜欢
Handwritten online chat system (principle part 1)
用于远程医疗的无创、无袖带血压测量【翻译】
美庐生物IPO被终止:年营收3.85亿 陈林为实控人
[Matlab] Simulink 同一模块的输入输出的变量不能同名
监控界的最强王者,没有之一!
Optical blood pressure estimation based on PPG and FFT neural network [translation]
Noninvasive and cuff free blood pressure measurement for telemedicine [translation]
The role of applet in industrial Internet
二叉搜索树
Top command details
随机推荐
同宇新材冲刺深交所:年营收9.47亿 张驰与苏世国为实控人
First, look at K, an ugly number
Some recruitment markets in Shanghai refuse to recruit patients with covid-19 positive
Optical blood pressure estimation based on PPG and FFT neural network [translation]
There is a sound prompt when inserting a USB flash disk under win10 system, but the drive letter is not displayed
随着MapReduce job实现去加重,多种输出文件夹
C#/VB. Net to add text / image watermarks to PDF documents
Interpreting cloud native technology
ORACLE进阶(四)表连接讲解
图片缩放中心
STM32+ENC28J60+UIP协议栈实现WEB服务器示例
用于远程医疗的无创、无袖带血压测量【翻译】
Tree-LSTM的一些理解以及DGL代码实现
287. 寻找重复数
Mathematics in machine learning -- common probability distribution (XIII): Logistic Distribution
Shangsilicon Valley JUC high concurrency programming learning notes (3) multi thread lock
AFNetworking框架_上传文件或图像server
[the 300th weekly match of leetcode]
当保存参数使用结构体时必备的开发技巧方式
Splay