首页 > 代码库 > UVa 129 (回溯法) Krypton Factor

UVa 129 (回溯法) Krypton Factor

回溯法确实不是很好理解掌握的,学习紫书的代码细细体会。

技术分享
 1 #include <cstdio> 2  3 char S[100]; 4 int n, L, cnt; 5  6 int dfs(int cur) 7 { 8     if(cnt++ == n) 9     {10         for(int i = 0; i < cur; ++i)11         {12             if(i % 64 == 0 && i) puts("");13             else if(i % 4 == 0 && i) printf(" ");14             printf("%c", A + S[i]);15         }16         printf("\n%d\n", cur);17         return 0;18     }19     for(int i = 0; i < L; ++i)20     {21         S[cur] = i;22         int ok = 1;23         for(int j = 1; j*2 <= cur + 1; ++j)24         {25             int equal = 1;26             for(int k = 0; k < j; ++k)27                 if(S[cur-k] != S[cur-k-j]) { equal = 0; break; }28             if(equal) { ok = 0; break; }29         }30         if(ok) if(!dfs(cur+1)) return 0;31     }32     return 1;33 }34 35 int main()36 {37     while(scanf("%d%d", &n, &L) == 2 && n)38     {39         cnt = 0;40         dfs(0);41     }42 43     return 0;44 }
代码君

 

UVa 129 (回溯法) Krypton Factor