【蓝桥杯】第七届国赛C语言B组 2.凑平方数（dfs+STL）

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 
 4 using namespace std;
 5 
 6 int a[10] = {0,1,2,3,4,5,6,7,8,9};
 7 ll n1[10];
 8 set<string>s;
 9 
10 void dfs(int step,int num)
11 {
12     if(step == 10)   // 用完了10个数
13     {
14         ll n2[10];
15         for(int i = 0;i < num;i++)
16         {
17              n2[i] = n1[i];
18         }
19         sort(n2,n2+num);
20         string xu;
21         char str[100];
22         for(int i = 0;i < num;i++)
23         {
24             sprintf(str,"%lld",n2[i]);   // 转换成字符串
25             xu += str;
26             xu += "-";
27         }
28         cout << xu << endl;
29         s.insert(xu);   
30         return ;
31     }
32     if(a[step] == 0)
33     {
34         n1[num] = 0;
35         dfs(step+1,num+1);
36     }
37     else
38     {
39         ll sum  = 0;
40         for(int i = step;i < 10;i++)
41         {
42             sum = sum*10+a[i];   // 算出当前所得到的值
43             double son = sqrt(sum);
44             if(son == (int)son)
45             {
46                 n1[num] = sum;
47                 dfs(i+1,num+1);
48             }
49         }
50     }
51 }
52 
53 int main()
54 {
55     do
56     {
57         memset(n1,0,sizeof(n1));
58         dfs(0,0);
59     }
60     while(next_permutation(a,a+10));
61     cout << s.size() << endl;
62     return 0;
63 }