Prime Ring Problem HDU - 1016

这道题是比较典型的dfs，在这里总结一下dfs的模板思路：
1、给dfs一个初始进入点
2、对后面的点进行一个遍历
3、对符合要求的点进行下一步的dfs（注意此层dfs结束后要释放flag）
4、设定return条件

这道题还有一个比较恶心的地方，杭电的oj每一个答案的最后不能带空格，不然一直判输出格式错误，代码中有注释。

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

int n;
int one[41]={0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0};
int ans[23]={0};
int flag[30]={0};
int x=1,y=1;


void dfs(int num){
    if(num==n+1 && one[ans[num-1]+ans[1]]==1){
        for(int i=1; i<=n; i++){
            if(i>1)
                cout<<" ";//加入这个
            cout<<ans[i];
        }
        cout<<endl;

    }
        for(int i=2; i<=n; i++){

            if(flag[i]==0 && one[i+ans[num-1]]==1){
                ans[num] = i;
                flag[i] = 1;
                dfs(num+1);
                flag[i]=0;
            }
        }
}


int main(){
    //scanf("%d", &n);
    int temp=1;
    while(cin>>n){
        cout<<"Case "<<temp<<":"<<endl;
        ans[1] = 1;
        memset(flag, 0, sizeof(flag));
        dfs(2);
        temp++;
        cout<<endl;
    }
}