现在的位置: 首页 > 算法 > 正文

poj 2362 || zoj 1909 Square (DFS+剪枝)

2018年09月22日 算法 ⁄ 共 1524字 ⁄ 字号 评论关闭

题目链接:http://poj.org/problem?id=2362

题目大意:给出M条筷子,问是否能够拼凑成正方形,是则打印yes,否则no.

解题思路:范围4 <= M <= 20,可以直接用DFS,DFS需要剪枝,否则肯定超时.
                  剪枝:1.总数不能被4整除,直接打印 no;
                             2.最长的那个筷子大于平均数,直接打印 no;
                         ***3.从某点出发,走了很多个点,如果会返回那么直接退出此次循环(因为出发点不满足题意);
                             4.返回之后(说明走此点不合题意),若for循环的下一个点的值和现在一样,那么跳过下一个点;

                             5.当可以构成3条长度等于average就直接退出打印yes;

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 21
int num,flag,t,n,m,average,visit[MAX],stick[MAX];

int cmp(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}

void DFS(int start,int temp,int root)
{
    int i,j;
    if(flag!=0)
        return ;
    if(temp==average)
    {
        num++;
        if(num==3) //剪枝5
        {
            flag=1;
            return ;
        }
        j=0;
        while(visit[j])  //**如果从没有访问过的那个点开始
            j++;
        DFS(j,0,j);
        return ;
    }
    for(i=start;i<n;i++)
    {
        if(visit[i]==0&&stick[i]+temp<=average)
        {
            visit[i]=1;
            DFS(i+1,temp+stick[i],root);
            //以下表示已经退回来了// 既还原现场!!!
            if(flag) //找到符合的就退出所有DFS
                return ;
            if(temp+stick[i]==average) //如果走的点总有把num++,那么退回来的时候要还原(num--)
            {
                num--;
            }
            visit[i]=0;
            while(stick[i]==stick[i+1])  //剪枝4 返回之后(说明走此点不合题意),若for循环的下一个点的值和现在一样,那么跳过下一个点
                i++;
        }
        if(!visit[root]) //**剪枝3 从某点出发,走了很多个点,如果会返回那么直接退出此次循环
            return ;
    }
}

int main()
{
    int i,sum,max;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=0,sum=0,max=0,average=0;i<n;i++)
        {
            scanf("%d",&stick[i]);
            sum+=stick[i];
            if(stick[i]>max)
                max=stick[i];
        }
        average=sum/4;
        if(sum%4!=0||max>average)  //剪枝1,剪枝2
        {
            printf("no\n");
            continue;
        }
        memset(visit,0,sizeof(visit));
        qsort(stick,n,sizeof(stick[0]),cmp);
        flag=0;
        num=0;
        DFS(0,0,0);
        if(flag==1)
            printf("yes\n");
        else
            printf("no\n");
    } 
    return 0; 
}

注:原创文章,转载请注明出处

 

抱歉!评论已关闭.