更深層次的DFS 解決POJ 2362
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".
Sample Input
3
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5
Sample Output
yes
no
yes
//qsort的用法
//qsort(數組名,數組大小,數組的類型,比較的函數)
//比較的函數的定義,見19行
View Code
#include <stdio.h> #include <stdlib.h> #include <string.h> int part, N; int len[128]; char used[128]; int cmp(const void *a, const void *b) //qsort的自定義函數 { return *(int *)b - *(int *)a; } int dfs(int side, int start, int sidelength) { int i; if (sidelength==0) { sidelength = part; //再次賦值為邊長的大小 side++; //用來統計滿足條件的邊的個數 start = 0; } if (side == 4) //函數的出口,當有4個邊時,正好構成正方形,返回真,作整個DFS的出口 return 1; for (i = start; i < N; i++) { if (len[i] > sidelength || used[i] ) //大于邊長 或者 已經被用過 continue; used[i] = 1; //否則將其標記為已經用過 if (dfs(side, i + 1, sidelength - len[i])) { return 1; //只有當30行的return 1執行之后,才會執行這里的return 1;結束DFS } used[i] = 0; } return 0; } int solve() { int i, sum; scanf("%d", &N); sum = 0; for (i = 0; i < N; i++) { scanf("%d", &len[i]); sum += len[i]; } // 1 if (sum % 4) return 0; part = sum / 4; qsort(len, N, sizeof(len[0]), cmp); //數組名,數組大小,數組的類型,比較的函數 // 2 if (len[0] > part) return 0; memset(used, 0, N); return dfs(0, 0, part); } int main() { int t; scanf("%d", &t); while (t--) printf("%s\n", solve() ? "yes" : "no"); return 0; }
posted on 2011-09-07 08:35 More study needed. 閱讀(250) 評論(0) 收藏 舉報

浙公網安備 33010602011771號