【dfs】hdu 1016 Prime Ring Problem

题目链接

刚开始接触搜索，先来一道基本题目练练手。

• 注意对树的深度进行dfs
• dfs过程中注意回退！！！
• 素数提前打表判断快一些

参考代码

/*Author:Hacker_vision*/
#include<bits/stdc++.h>
#define clr(k,v) memset(k,v,sizeof(k))
using namespace std;

const int _max=1e3+10;//素数打表
int n,pri[]={0,0,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};
bool vis[_max];
int v[_max];//存储序列

void dfs(int deep){ //对树的深度
  if(deep==n&&pri[v[deep-1]+1]==1){ //递归基，这里用作输出
    int i;for(i=0; i< n-1; ++i ) cout<<v[i]<<" ";cout<<v[i]<<endl;
    return;
  }
  for(int i=2; i <= n; ++ i) 
    if(!vis[i]&&pri[i+v[deep-1]]==1){
        vis[i]=true;
        v[deep]=i;  //访问这个节点
        dfs(deep+1); //深度自加
        vis[i]=false; //该节点会出现在其他同深度节点的树林中，回退！！关键啊
    }
}

int main(){
 //freopen("input.txt","r",stdin);
 int cnt=1;
 while(cin>>n){
    clr(vis,0);
    v[0]=1;
    printf("Case %d:\n",cnt++);
    dfs(1);
    puts("");
 }
 return 0;
}

• 加粗 Ctrl + B
• 斜体 Ctrl + I
• 引用 Ctrl + Q
• 插入链接 Ctrl + L
• 插入代码 Ctrl + K
• 插入图片 Ctrl + G
• 提升标题 Ctrl + H
• 有序列表 Ctrl + O
• 无序列表 Ctrl + U
• 横线 Ctrl + R
• 撤销 Ctrl + Z
• 重做 Ctrl + Y