-DFS- [CodeVS P3880]环素数

题目描述

给定一个N(1<=N<=10)，求1——N组成的环，使得环上相邻的元素和为素数。

输入描述

一个整数N

输出描述

把1放在第一位置，按照字典顺序不重复地输出所有解（顺时针，逆时针算不同的两种），相邻两数之间严格用一个空格隔开，每一行的末尾不能有多余的空格。如果无解，则输出“no”。

样例输入

8

样例输出

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

Solution

运用DFS，代码中会详细解释。

Code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
using namespace std;
int n,a[15]= {0};
bool used[15]= {0},flag=0;
bool chk_prime(int a) {//用于判断素数的函数
    if(a==2) return 1;
    if(a==1) return 0;
    if(a==0) return 0;
    for(int i=2; i<=sqrt(a); i++) {
        if(a%i==0) return 0;
    }
    return 1;
}
bool chk() {//用于判断是否符合条件的函数
    int p=0;
    for(int i=1; i<=n-1; i++) {
        if(chk_prime(a[i]+a[i+1])==1) {
            p++;
        }
    }
    if(chk_prime(a[n]+a[1])==1) p++;
    if(p==n) return 1;
    else return 0;
}
void print() {//用于打印的函数
    for(int i=1; i<=n-1; i++) {
        printf("%d ",a[i]);
    }
    printf("%d\n",a[n]);
    flag=1;//标记存在答案
}
void dfs(int i) {//进行深度优先搜索(DFS)
//	print();
    for(int j=2; j<=n; j++) {
        if(used[j]==0) {//如果这个数没用过
            a[i]=j;//那就使用这个数
            used[j]=1;//把这个数标记为用过
            if(i==n) {
                if(chk()==1) {
                    print();//打印答案
                }
            }
                        else dfs(i+1);
            /*回溯部分*/
                        used[j]=0;
            a[i]=0;
        }
    }
}
int main() {
    cin>>n;
    a[1]=1;
    used[1]=1;
    dfs(2);//进行DFS
    if(flag==0){//如果没有答案，就输出no
        cout<<"no";
    }
    return 0;//程序结束
}