uva 524 Prime Ring Problem

题目：Prime Ring Problem

题意：求长度为n的素数环。

思路：dfs，枚举每一位上的值。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;bool Prime[33]={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};
int n;
vector<int> vec;
int use[33]={0};void dfs(int x){if(x==n){if(!Prime[vec[vec.size()-1]+1]) return ;printf("1");for(int i=1;i<vec.size();i++){printf(" %d",vec[i]);}printf("\n");return ;}for(int i=2;i<=n;i++){if(!use[i]&&Prime[vec[x-1]+i]){use[i]=true;vec.push_back(i);dfs(x+1);use[i]=false;vec.pop_back();}}
}int main() {int T=0;while(scanf("%d",&n)==1) {if(T!=0) printf("\n");vec.clear();vec.push_back(1);printf("Case %d:\n",++T);dfs(1);}return 0;
}