HDOJ1016 素数环（DFS）

  1 /*
  2 素数环（顺时针逆时针）---dfs
  3 使用栈
  4 1-n（n最大是20，相邻最大和39，素数范围2-39之间）
  5 2-39间的素数：
  6 2，3，5，7，11，13，17，19，23，29，31，37
  7 从1开始，逐个尝试，如果是素数，入栈，否则尝试下一个，直到全部尝试完；
  8 如果n个数全部入栈了，输出一组解（n最大为20，输出栈可以使用递归），
  9 第一个数始终是1，第二个数需要尝试n+1的时候，就表示结束了（next = -1）。
 10 */
 11 #include <cstdio>
 12 #include <iostream>
 13 #include <stack>
 14 using namespace std;
 15 
 16 #define N    22
 17 //全局变量
 18 int prime[40];
 19 int arr[N];
 20 stack<int> s;
 21 
 22 //函数
 23 void InitPrime();
 24 void InitArr(int n);
 25 void dfs(int n);
 26 int GetNext(int b,int n);
 27 void Output(int n);
 28 //main
 29 void main()
 30 {
 31     int n;
 32     InitPrime();
 33     while (scanf("%d",&n)!=EOF)
 34     {
 35         InitArr(n);
 36         dfs(n);
 37     }
 38 }
 39 
 40 void InitPrime()
 41 {
 42     for (int i=0;i<40;i++)
 43     {
 44         switch(i)//本题数量不多，就直接这样写啦，如果数量多可以用【筛选法】或者【试除法】
 45         {
 46         case 2:        case 3:        case 5:
 47         case 7:        case 11:    case 13:
 48         case 17:    case 19:    case 23:
 49         case 29:    case 31:    case 37:
 50             prime[i] = 1;
 51             break;
 52         default:
 53             prime[i] = 0;
 54         }
 55     }
 56 }
 57 
 58 void InitArr(int n)
 59 {
 60     for (int i=1; i<=n ; i++)
 61     {
 62         arr[i] = 0;
 63     }
 64 }
 65 void dfs(int n)
 66 {
 67     int flag,next,b,idx;
 68     s.push(1);
 69     arr[1] = 1;
 70     flag = 1;
 71     idx = 1;//从idx开始寻找匹配数字
 72     while (flag)
 73     {
 74         b = s.top();
 75         next = GetNext(idx,n);
 76         if (next == -1)//尝试结束，回溯
 77         {
 78             if (b == 1 && next == -1)//over
 79             {
 80                 flag = 0;
 81             }
 82             idx = s.top();
 83             s.pop();
 84             arr[idx] = 0;
 85             continue;
 86         }
 87         if (prime[next+b] == 1)//匹配成功，next入栈，idx化为2
 88         {
 89             arr[next] = 1; 
 90             s.push(next);
 91             idx = 1;
 92             //全部入栈则输出
 93             if (s.size() == n && prime[1+s.top()] == 1)//既要顺时针为素数环又要逆时针为素数环
 94             {
 95                 Output(n);
 96                 cout<<endl;
 97                 idx = s.top();
 98                 s.pop();
 99                 arr[idx] = 0;
100             }    
101             continue;
102         }
103         //匹配失败，idx化为next
104         idx = next;
105     }
106 
107 }
108 int GetNext(int b,int n)
109 {
110     for (int i=b+1;i<=n;i++)
111     {
112         if (arr[i]!=1)
113             return i;
114     }
115     return -1;//全部尝试完返回-1
116 }
117 void Output(int n)
118 {
119     int cur;
120     if (n!=0)
121     {
122         cur = s.top();
123         s.pop();
124         Output(n-1);
125         cout<<cur<<' ';
126         s.push(cur);//还要加回去
127     }
128 }