python/TangDou/Dfs/DFS9_SuShuHuan.cpp

#include <bits/stdc++.h>

using namespace std;
/**
 测试用例：
 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
 */

const int N = 30;
int a[N];
int st[N];
int n = 8;

//判断一个数是不是质数
bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i <= n / i; i++)
        if (n % i == 0) return false;
    return true;
}

void dfs(int step) {
    if (step == n + 1) {
         if (isPrime(a[n] + 1)) {
            for (int i = 1; i <= n; i++)printf("%d ", a[i]);
            printf("\n");
        }
        return;
    }
    for (int i = 2; i <= n; i++)
        if (!st[i] && isPrime(a[step - 1] + i)) {
            st[i] = true;
            a[step] = i;
            dfs(step + 1);
            st[i] = false;
        }
    }

int main() {
    //第一个位置写死，占上，不能改
    a[1] = 1;
    //开始深度优先搜索
    dfs(2);
    return 0;
}