Safecracker

问题陈述：

　　杭州电子科技大学HANGZHOU DIANZI UNIVERSITY Online Judge Problem - 1015

问题解析：

　　深度优先搜索(Depth_First Search)

代码详解：　　

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 using namespace std;

 int flag, visited[];

 int cmp(const void *a, const void *b){

     return *(char *)b - *(char *)a;

 }

 int calculate(char *ans) {

     int res = , x = , sign = ;

     for(int i=; i<; i++) {

         for(int j=; j<=i; j++) {

             x *= (ans[i] - 'A' + );

         }

         res += x * sign;

         x = ;

         sign *= (-);

     }

     return res;

 }

 void dfs(char *str, int target, char *ans, int depth, int len) {

     if(depth == ) {

         if(calculate(ans) == target)

             flag = ;

         return;

     }

     for(int i=; i<len; i++) {

         if(!visited[i]) {

             ans[depth] = str[i];

             visited[i] = ;

             dfs(str, target, ans, depth+, len);

             if(flag)

                 return;

             visited[i] = ;

         }

     }

 }

 int main()

 {

     int target;

     char ans[], str[];

     while(scanf("%d %s", &target, str)!=EOF && !(target== && strcmp(str, "END")==)) {

         memset(visited, , sizeof(visited));

         qsort(str, strlen(str), sizeof(char), cmp);

         flag = ;

         dfs(str, target, ans, , strlen(str));

         if(flag){

             ans[] = '\0';

             puts(ans);

         } else {

             puts("no solution");

         }

     }

     return ;

 }

参考博客：CSDN Kizuki

转载请注明出处：http://www.cnblogs.com/michaelwong/p/4315092.html