hdu 1518(dfs)

題目鏈接 ：http://acm.hdu.edu.cn/showPRoblem.php?pid=1518

Square

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5  6 int a[22],vis[22]; 7 int n,m,length;               //length表示要組成的正方形的邊長(zhǎng) 8 int ans,flag; 9 10 void dfs(int cnt,int sum, int k)   //cnt記錄邊數(shù)，sum記錄當(dāng)前邊長(zhǎng)，k記錄位置11 {12     if (cnt == 3)               //如果有三條邊滿足要求，那么第四條邊一定滿足要求13     {14         flag = 1;15         return ;16     }17     if (sum == length)        //找到滿足要求的邊，邊數(shù)加一，初始化18     {19         cnt++;20         k = 0;21         sum = 0;22     }23     for (int i=k; i<m; i++)24     {25         if (!vis[i] && sum + a[i] <= length)26         {27             vis[i] = 1;28             dfs(cnt, sum+a[i], i+1);29             if (flag)         //優(yōu)化時(shí)間，（當(dāng)找到所有邊之后就一直返回，不需要再把之后的代碼運(yùn)行一遍）30             {31                 return ;32             }33             vis[i] = 0;34         }35     }36 }37 38 int main ()39 {40     scanf ("%d",&n);41     while (n--)42     {43         ans = 0;44         scanf ("%d",&m);45         for (int i=0; i<m; i++)46         {47             scanf ("%d",&a[i]);48             ans += a[i];49         }50         if (ans % 4)              //如果所有邊長(zhǎng)和不是4的倍數(shù)，怎樣都不能組成正方形51         {52             printf ("no/n");53             continue ;54         }55         memset(vis, 0, sizeof(vis));56         flag = 0;57         length = ans / 4;     //記錄正方形邊長(zhǎng)58         dfs(0, 0, 0);59         if (flag)60             printf ("yes/n");61         else62             printf ("no/n");63     }64     return 0;65 }