poj2362 Square（DFS）

题目链接

题意

输入n根棍子的长度，求这n根棍子是否能组成一个正方形。

思路

假设能组成正方形，则正方形的周长为sum，sum/4为正方形的边长，问题转化为这n根棍子能否组成4根长度为side的棍子。由于棍子的长度越长，组合的灵活性就越差，所以将n根棍子按从长到短排序后dfs。

代码

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <vector>
 6 using namespace std;
 7 
 8 const int N = 30;
 9 vector<int> stick;
10 int visit[N];
11 int n;
12 int side;
13 
14 bool cmp(int a, int b)
15 {
16     return a>b;
17 }
18 
19 bool dfs(int num, int len, int cur)
20 {
21     if(num==4)
22         return true;
23 
24     for(int i=cur; i<n; i++)
25     {
26         if(visit[i])
27             continue;
28         visit[i] = 1;
29         if(len+stick[i]==side)
30         {
31             if(dfs(num+1, 0, 0))
32                 return true;
33         }
34         else if(len+stick[i]<side)
35         {
36             if(dfs(num, len+stick[i], i+1))
37                 return true;
38         }
39         visit[i] = 0;
40     }
41     return false;
42 }
43 
44 int main()
45 {
46     //freopen("poj2362.txt", "r", stdin);
47     int t;
48     cin>>t;
49     while(t--)
50     {
51         int sum = 0;
52         stick.clear();
53         cin>>n;
54         for(int i=0; i<n; i++)
55         {
56             int len;
57             cin>>len;
58             sum += len;
59             stick.push_back(len);
60         }
61         side = sum / 4;
62         sort(stick.begin(), stick.end(), cmp);
63         if(sum%4!=0 || side<stick[0])  
64         {
65             cout<<"no"<<endl;
66             continue;
67         }
68         memset(visit, 0, sizeof(visit));
69         bool ans = dfs(1, 0, 0);
70         if(ans)
71             cout<<"yes"<<endl;
72         else cout<<"no"<<endl;
73     }
74     return 0;
75 }

相似题目

1、poj1011：该题的增强版。

参考

1、http://blog.csdn.net/xindoo/article/details/8867919