欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Square 北大POJ2362 深度优先搜索相关 计算机考研机试指南整理

程序员文章站 2022-07-16 09:39:11
...

Square 北大POJ2362 深度优先搜索相关 计算机考研机试指南整理
Square 北大POJ2362 深度优先搜索相关 计算机考研机试指南整理

Square 北大POJ2362 深度优先搜索相关 计算机考研机试指南整理

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXN = 25;

int sticks[MAXN];
bool visit[MAXN]; 
int m;
int side;

bool Compare(int x,int y){
	return x>y;
}

bool DFS(int sum,int number,int position){ //sum 当前拼凑的木棍长度,number 已拼凑出的边长,position 当前木棍的编号 
	if(number == 3){
		return true;
	}
	int sample = 0 ; //记录失败的木棍长度,下次再遇到直接跳过。 
	for(int i = position; i  < m ; i++){  //从上一位置接着寻找 
		if(visit[i] || sum +sticks[i] > side || sticks[i] == sample){//在凑成一条边的路径中 
			continue;
		} 
		visit[i] = true;
		if(sum + sticks[i] == side){ //一条边已经凑齐 
			if(DFS(0,number+1,0)){  //当一条边已经凑齐了之后,重新开始另一条边要从头开始查找可以使用的木棍 
				return true;
			}else {
				sample = sticks[i];
			}
		} else {
			if(DFS(sum + sticks[i],number,i+1)){  //一条边没有凑齐,继续凑下一个木棍 
				return true; 
			}else {
				sample = sticks[i];
			}
		}
		visit[i] = false;
	} 
	return false;
} 

int main()
{
	int n ;cin>>n;
	while(n--){
		cin>>m;
		int length =0;
		for(int i = 0 ; i < m; i++){
			cin>>sticks[i];
			length += sticks[i];
		}
		if(length % 4 != 0){
			cout<<"no"<<endl;
			continue;
		}   
		side = length/4;
		sort(sticks,sticks + m,Compare);
		if(sticks[0] > side){
			cout<<"no"<<endl;
			continue;
		}
		memset(visit,false,sizeof(visit));
		if(DFS(0,0,0)){
			cout<<"yes"<<endl;
		}else {
			cout<<"no"<<endl;
		}
		
	}
	return 0;
}
相关标签: 算法刷题 算法