HDU 1016 Prime Ring Problem (DFS(深度優先搜索))

Prime Ring Problem
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 20489 Accepted Submission(s): 9159

Problem Description
A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.

Input
n (0 < n < 20).

Output
The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.

You are to write a program that completes above process.

Print a blank line after each case.

Sample Input
6
8

Sample Output
Case 1:
1 4 3 2 5 6
1 6 5 2 3 4

Case 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

題目大意： 判斷 1-n   相鄰兩個數相加的和是不是素數，輸出素數環
DFS 算法

import java.io.*;
import java.util.*;
public class Main {
	public static int n;
	public static boolean mark[];
	public static int a[];
	public static PrintWriter pw;
	public static void main(String[] args) {
		Scanner sc=new Scanner(new BufferedInputStream(System.in));//輸入
		pw=new PrintWriter(new BufferedOutputStream(System.out),true);//輸出
		int number=1;
		while(sc.hasNextInt()){
			n=sc.nextInt();
			mark=new boolean[n+1];
			a=new int[n+1];
			mark[1]=true;
			a[0]=1;
			pw.println("Case "+number+++":");
			DFS(1);
			pw.println();
		}
	}
	public static void DFS(int len){
		
		if(len==n){
			//判斷第一個元素和最後一個元素是不是素數
			if(isPrime(a[0]+a[n-1])){
				for(int i=0;i<n-1;i++){
					pw.print(a[i]+" ");
				}
				pw.println(a[n-1]);
			}
			return;
		}
			for(int i=2;i<=n;i++){
				
				if(!mark[i]&&isPrime(a[len-1]+i)){//判斷相鄰兩個元素是不是素數
					mark[i]=true;
					a[len]=i;
					DFS(len+1);
					mark[i]=false;//回溯
				}
			}
		
	}
	//判斷是不是素數
	public static boolean isPrime(int m){
		for(int i=2;i<=Math.sqrt(m);i++){
			if(m%i==0)
				return false;		
		}
		return true;
	}
}