当前位置:编程学习 > C/C++ >>

hdu 1518 Square(DFS)

题目大意:所有的木棒连在一起,看能够组成一个正方形

也是一道比较经典的DFS,刚做过hdu1455(1455题解:1455题解)那道题,方法都一样,比这道难,现在做这道题感觉很easy

 

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,map[25],v[25];
int sum,length,flag;
bool cmp(int x,int y)
{
    return x > y;
}
void dfs(int num,int len,int pos)
{
    if(num == 4)
    {
        flag = 1;
        return;
    }
    if(flag) return;
    for(int i = pos ; i < n ; i ++)
    {
        if(v[i]) continue;
        if(map[i] + len == length)
        {
            v[i] = 1;
            dfs(num + 1,0,0);
            v[i] = 0;
        }
        else if(map[i] + len < length)
        {
            v[i] = 1;
            dfs(num,map[i] + len,i + 1);
            v[i] = 0;
            while(map[i] == map[i + 1])
            i++;
        }
    }
}
int main()
{
    int i,T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        sum = 0 ;
        for(i = 0 ; i < n ; i ++)
        {
            scanf("%d",&map[i]);
            sum += map[i];
        }
        sort(map,map + n,cmp);
        if(sum%4)
        {
            printf("no\n");
            continue;
        }
        memset(v,0,sizeof(v));
        length = sum/4;
        flag = 0;
        dfs(1,0,0);
        if(flag) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}

 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,