HOJ 1016 / UVA 524 Prime Ring Problem（算法竞赛入门经典，深搜）

算法竞赛入门经典194页，深搜
题目意思： n 个数， 从 1 到 n ， 要求排成一圈，使得相邻数的和是素数。 求出所有的排列方式，
其中 1 必须在第一位。按字典序输出所有的排列方式。

本题要点：
1、n <= 20, 可以暴力搜。 显然，只有n是偶数的情况，才可能存在这种排列方式。
2、用 vector 来存每一种方式， 再用 set<vector > 来排序。
3、素数的处理， 用数组 isprime[i] 表示 i 是否是素数。
4、vis[i]表示 第i个数字，是否已经选择， cycle[i] 表示，排列的第 i 个数 是哪个。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
const int MaxN = 25;
int n;
int prime[14] = {
    3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
bool isprime[50];
bool vis[MaxN];
int cycle[MaxN];
set<vector<int> > s;// 前 1 ~ indx - 1 个位置已经确定 
void dfs(int indx)
{
    if(indx > n && isprime[cycle[1] + cycle[n]])	// 得到一组解 {
    vector<int>	 v;for(int i = 1; i <= n; ++i)v.push_back(cycle[i]);s.insert(v);return;}// indx 这个位置可以填哪个for(int i = 2; i <= n; ++i){
    if(!vis[i] && isprime[i + cycle[indx - 1]])	// 假设 indx 填 i{
    vis[i] = 1;cycle[indx] = i;dfs(indx + 1);vis[i] = 0;}}
}void print()
{
    for(set<vector<int> >::iterator it = s.begin(); it != s.end(); ++it){
    int len = it->size();printf("%d", (*it)[0]);for(int i = 1; i < len; ++i){
    printf(" %d", (*it)[i]);}printf("\n");}
}int main()
{
    for(int i = 0; i < 14; ++i){
    isprime[prime[i]] = 1;}int cnt = 0;while(scanf("%d", &n) != EOF){
    printf("Case %d:\n", ++cnt);s.clear();memset(vis, 0, sizeof vis);vis[1] = 1, cycle[1] = 1;dfs(2);print();printf("\n");}return 0;
}/* 6 8 *//* Case 1: 1 4 3 2 5 6 1 6 5 2 3 4Case 2: 1 2 3 8 5 6 7 4 1 2 5 8 3 4 7 6 1 4 7 6 5 8 3 2 1 6 7 4 3 8 5 2*/