Vjudge Prime Ring Problem (dfs)

ゝ一纸荒年。 2024-02-18 16:32 39阅读 0赞

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.  
  
![427b1dd2282412709d583cc17eda983e_v_1510614455][]

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

AC代码：

#include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    using namespace std;
    int path[20+2];
    int vis[20+2];
    int n;
    
    bool isPrime(int t){
    	for(int i = 2; i <= sqrt(t);i++){
    		if(t % i == 0) return false;
    	}
    	return true;
    }
    
    void dfs(int cnt){
    	if(cnt - 1 == n) {
    		if(isPrime(path[1] + path[n])){
    					printf("%d",path[1]);
    					for(int i = 2; i <= n; i++)
    					printf(" %d",path[i]);
    					printf("\n");
    				}
    	    return ;
    	}
    	for(int j = 2; j <= n; j++){
    		if(!vis[j] && isPrime(path[cnt-1] + j)){
    			vis[j] = 1;
    			path[cnt] = j;
    			dfs(cnt + 1);
    			vis[j] = 0;
    		}
    	}
    }
    
    int main(){
    	int count = 0;
    	while(scanf("%d",&n)==1){
    		printf("Case %d:\n",++count);
    		memset(vis,0,sizeof(vis));
    		path[1] = 1;
    		vis[1] = 1;
    		for(int i = 2; i <= n; i++){
    			if(isPrime(path[1]+i)){
    				path[2] = i;
    				vis[i] = 1;
    				dfs(3);
    				vis[i] = 0;
    			}
    		}
    		
    		printf("\n");
    	}
    	return 0;
    }

[427b1dd2282412709d583cc17eda983e_v_1510614455]: https://odzkskevi.qnssl.com/427b1dd2282412709d583cc17eda983e?v=1510614455