王道机试指南 例题9.4 Square

题目：

题目大意：给出一堆长度各异的木条，这些木条能否头尾相连构成一个正方形？

算法及分析：

深度优先遍历。

代码：

#include <iostream>
#include <string>
#include <cstring> //memset函数的头文件
#include <algorithm>

using namespace std;

//设计成全局变量，减少DFS函数的传参数量
const int MAXN=25;
int side;//正方形边长
int m;//木条数
int sticks[MAXN];//记录木条长度
int visit[MAXN];//记录该木条是否访问过

bool DFS(int sum,int count,int position){//深度优先遍历
    if(count==3)
        return true;
    for(int i=position;i<m;i++){
        if(visit[i]==1 || sum+sticks[i]>side)//如果该条边访问过或累加后长度大于正方形边长，则进入下一轮循环
            continue;

        sum+=sticks[i];
        visit[i]=1;
        if(sum==side){//刚好凑成一条边
            if(DFS(0,count+1,0)==1)
                return true;
        }
        else{//sum<side，还不够凑成一条边
            if(DFS(sum,count,i+1)==1)
                return true;
        }
        //本轮构造失败，则恢复sum并恢复访问标记
        sum-=sticks[i];
        visit[i]=0;
    }
    return false;
}

bool compare(int x,int y){//按从大到小排序
    return x>y;
}

int main(){
    int n;
    cin>>n;
    for(int k=0;k<n;k++){
        cin>>m;
        int total=0;
        for(int j=0;j<m;j++){
            cin>>sticks[j];
            total+=sticks[j];
        }

        if(total%4!=0){//剪枝：如果总长度不能被4整除，则构造失败
            cout<<"no"<<endl;
            continue;
        }

        side=total/4;
        sort(sticks,sticks+m,compare);//将木条按长度从大到小排序
        if(sticks[0]>side){//剪枝：如果最长的木条长度超过正方形边长，则构造失败
            cout<<"no"<<endl;
            continue;
        }

        memset(visit,0,sizeof(visit));//初始化访问标记为0
        if(DFS(0,0,0)==1)
            cout<<"yes"<<endl;
        else
            cout<<"no"<<endl;
    }
    return 0;
}

运行结果：