题解 | #Square#（DFS）

原题链接

Description

Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?

Input

The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number of sticks. M integers follow; each gives the length of a stick - an integer between 1 and 10,000.

Output

For each case, output a line containing "yes" if is is possible to form a square; otherwise output "no".

• 用递归实现dfs
• 多次“剪枝”:降低复杂度

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

using namespace std;
int n;//木棍数
int side;//边长
int stick[25];//每根木棍长度
bool visit[25];//访问标记
bool com(int x,int y){
  return x>y;
}

bool dfs(int len,int match,int pos){//目前拼凑长度、已拼成边数、查找起始位置
  if(match==3)return true;//拼出3边，剩下木棍必能拼成一边
  int fail=0;//本层拼凑失败的长度
  for(int i=pos;i<n;i++){
    if(len+stick[i]>side||visit[i]||stick[i]==fail)continue;//超长、被访问过、与同层失败长度相同
    visit[i]=true;
    if(len+stick[i]==side){
      if(dfs(0,match+1,0))return true;
      else fail=stick[i];//③
    }
    else{
      if(dfs(len+stick[i],match,i+1))return true;
      else fail=stick[i];//③
    }
    visit[i]=false;
  }
  return false;
}



int main(){
  int m;
  while(scanf("%d",&m)!=EOF){
    for(int i=0;i<m;i++){
      int sum=0;
      scanf("%d",&n);
      for(int i=0;i<n;i++){
        scanf("%d",&stick[i]);
        sum+=stick[i];//总长度
      }
    
      if(sum%4!=0){//①
        printf("no\n");
        continue;
      }
    
      side=sum/4;
      sort(stick,stick+n,com);//降序
      if(stick[0]>side){//②
        printf("no\n");
        continue;
      }
    
      memset(visit,false,sizeof(visit));
      if(dfs(0,0,0)){
        printf("yes\n");
        continue;
      }
      else {
        printf("no\n");
      }
    }
  }
    return 0;
}