【例题 7-4 UVA - 524】Prime Ring Problem

【链接】 我是链接,点我呀:)

【题意】

在这里输入题意

【题解】

预处理出所有的答案。
打表输出。

【代码】

import java.util.ArrayList;

import java.util.Iterator;

import java.util.Scanner;

public class Main {

    static int a[] = new int[20];

    static boolean bo[] = new boolean[20];

    static ArrayList<String>[] list = new ArrayList[20];

    static boolean is_prime(int x){

        for (int i = 2;i <= Math.sqrt(x);i++)

            if(x%i==0) return false;

        return true;

    }

    static void dfs(int n,int now){

        if (now>n){

            if (n==1 || is_prime(a[n]+a[1])){

                StringBuilder temp = new StringBuilder();

                for (int i = 1;i <= n;i++){

                    temp.append(a[i]);

                    if (i==n) temp.append('\n');else

                        temp.append(' ');

                }

                list[n].add(temp.toString());

            }

            return;

        }

        for (int i = 1;i <= n;i++)

            if (!bo[i] && (now==1 || is_prime(i+a[now-1]))){

                a[now] = i;

                bo[i] = true;

                dfs(n,now+1);

                bo[i] = false;

            }

    }

    public static void main(String[] args){

        for (int i = 1;i <= 16;i++)

            list[i] = new ArrayList<String>();

        for (int i = 1;i <= 16;i++){

            bo[1] = true;

            a[1] = 1;

            dfs(i,2);

        }

        Scanner cin = new Scanner(System.in);

        int n,kase = 0;

        while (cin.hasNext()){

            if (kase>0) System.out.println("");

            n = cin.nextInt();

            System.out.println("Case "+(++kase)+":");

            for (String x:list[n])

                System.out.print(x);

        }

    }

}