HDU1016 Prime Ring Problem

PS: 很基础的一道搜索题目，也不需要特殊的剪枝技术，数据还是挺弱的。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
bool is_prime(int x);
void getPrime(); // get Prime.
const int maxn = 25;
int prime[50]; // save prime.  hash。
int res[maxn]; // save result.
bool vis[maxn]; // mark if visited.
int n;
int Case;
//Accepted	1016	250MS	300K	1392 B	G++	Achiberx
void dfs(int parent, int lev)  {
    if(lev == n+1 && prime[1+res[n]]==1+res[n] && n>1) {
        printf("%d", res[1]);
        for(int j = 2; j <= n && n>=2; j++) {
            printf(" %d", res[j]);
        }
        printf("\n");
        return;
    }
    int i;
    for(i = 2; i <= n; i++) {
        int v = i+parent;
        if(!vis[i] && prime[v]==v) {
            res[lev] = i;
            vis[i] = true;
            dfs(i, lev+1);
            vis[i] = false;
        }
    }
}

int main()
{
    getPrime();
    Case = 1;
    while(scanf("%d", &n)!= EOF) {
        memset(res, 0, sizeof(res));
        memset(vis, false, sizeof(vis));
        res[1] = 1;
        vis[1] = true;
         printf("Case %d:\n", Case++);
        dfs(1, 2);// parent, nextIndex.
        printf("\n");
    }
    return 0;
}

bool is_prime(int x) {
    for(int i = 2; i <= x/2; i++) {
        if(x%i==0 && x!=i) return false;
        continue;
    }
    return true;
}
void getPrime() {
    for(int i = 2; i <= 45; i++) {
        bool ok = is_prime(i);
        if(ok){
            prime[i] = i;
        }
        else prime[i] = -1;
    }
}

HDU1016 Prime Ring Problem,布布扣,bubuko.com

HDU1016 Prime Ring Problem

原文：http://blog.csdn.net/achiberx/article/details/23743727