（深搜）HDU 1016-Prime Ring Problem

原题链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1016

感悟：

这题一看就是递归+深搜+回溯，本来的写的代码已经可以输出正确答案，但是大部分判断都是循环，怕过不了，结合其他一些博主的代码，优化了一下。特别是用flag表示是否数组这一招比较佩服，用内存换时间，本来还是列素数表，循环判断会多用很多时间。
对于回溯了解的还不是很多，目前看来是设置一个标识，在继续搜索之前开启一下，再在返回的时候取消
格式问题：每行后面不能留空，是每行之后空一行，不是两行间空一行。

c++代码：

 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstring>
 4 using namespace std;
 5 int prime[38]={0, 0, 1, 1, 0, 1, 0,
 6                1, 0, 0, 0, 1, 0, 1,
 7                0, 0, 0, 1, 0, 1, 0,
 8                0, 0, 1, 0, 0, 0, 0,
 9                0, 1, 0, 1, 0, 0, 0,
10                0, 0, 1,};
11 int line[25];
12 int vis[25];
13 int n;
14 bool isSu(int a);
15 void ss(int x);
16 int main(){
17     int time=0;
18     while (cin >> n){
19         memset(line, 0, sizeof(line));
20         memset(vis,0,sizeof(vis));
21         line[0] = 1;
22         vis[1]=1;
23         cout << "Case " << ++time << ":" << endl;
24         if(n%2==1){
25             cout << endl;
26             continue;
27 
28         }
29         ss(1);
30         cout << endl;
31     }
32     return 0;
33 }
34 bool isSu(int a){
35     if(prime[a]){
36         return true;
37     }
38     return false;
39 }
40 void ss(int x){
41     if (x == n&& isSu(line[x - 1] + line[0]) ){
42         for (int i = 0; i < n; i++){
43             cout << line[i];
44             if(i!=n-1){
45                 cout<<" ";
46             }
47         }
48         cout << endl;
49     }
50     else{
51         for (int i = 2; i <= n; i++){
52             if (!vis[i] && isSu(i+line[x-1])){
53                 line[x] = i;
54                 vis[i]=1;
55                 ss(x + 1);
56                 vis[i]=0;
57             }
58         }
59     }
60 
61 }