# HDU-1518 DFS水题
## [HDU-1518](http://acm.hdu.edu.cn/showproblem.php?pid=1518)
## 分析
这几条边加起来肯定得能**整除4**啊, 因为是正方形, 边长固定.
接下来就硬dfs.
每条边一个方向标记(dir), 一个长度标记(len), 边长为edge. **len==edge**时说明这条边造完了dir++, **len>edge**时剪枝.
其实看题解发现还有一处可以剪枝: 单条棍如果超过边长也肯定不行. *(支棱起来了.jpg*
## 代码
```cpp
// -------------- GLOBAL ----------------
int stick[30], n, sum, maxx, edge;
bool book[30];
// -------------- FUNC ----------------
bool dfs(int k, int len, int dir) {
if (len > edge) return false;
if (len == edge) {
++dir; // 转向
if (dir >= 3) // 最后一条不用判了
return true;
len = 0; // 换另一条边
k = 0; // 重新枚举k也得���零
}
for (int i = k; i < n; ++i) {
if (book[i]) continue;
book[i] = true;
if (dfs(i, len + stick[i], dir)) return true;
book[i] = false;
}
return false;
}
// -------------- MAIN ----------------
int main() {
ios_base::sync_with_stdio(false);
int T;
INI(T);
while (T--) {
bool res = true;
sum = 0, maxx = -INF;
fill0(book);
INI(n);
F0(i, n) {
INI(stick[i]);
sum += stick[i];
maxx = max(maxx, stick[i]);
}
edge = sum / 4;
if (sum % 4)
res = false;
else
res = dfs(0, 0, 0);
if (res)
printf("yes\n");
else
printf("no\n");
}
return 0;
}
```
![]()