square(dfs).cpp

来自「杭电acm解题报告2001---2099.」· C++ 代码 · 共 60 行

#include <cstdio>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

int t,n,sum,edge_len;
int len[30];
bool flag;

void dfs(int now, int edge,int pos)
{
	int i,j,t;

	if (edge == 3) {
		flag = true;
		return ;
	}
	for (i=pos;i<n;i++) {
		if (len[i] > 0) {
			t = len[i];
			len[i] = -1;
			j = now + t;
			if (j == edge_len) {
				dfs(0,edge+1,0);
			}
			else if (j < edge_len) {//注意下次起始i+1，前面i+1无法构造出解
				dfs(j, edge, i+1);
			}
			len[i] = t;
			if (flag || edge_len < j) {
				return ;
			}
		}
	}
}

int main()
{
	int i,j;

	scanf("%d",&t);
	while (t --) {
		scanf("%d",&n);
		sum = 0;
		for (i=0;i<n;i++) {
			scanf("%d",&len[i]);
			sum += len[i];
		}
		sort(len,len+n);
		flag = false;
		if (sum % 4 == 0) {
			edge_len = sum / 4;
			if (edge_len >= len[n-1]) {
				dfs(0,0,0);
			}
		}
		printf("%s\n", flag ? "yes" : "no");
	}
}