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.
n (0 < n < 20).
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.
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
題目分析:
典型的 DFS 題目, 不需要 什么剪枝, 直接 窮舉 + 回溯 就OK了, 不過值得一提的是,這題輸出很BT, 一般的 前后 輸出 回車 , 第一個回車用
if( n == 1 ) 回車; 來做PE了好幾次, 最后直接在程序最后 輸出2個回車符竟然就A了, YM啊...........
代碼如下:
/*
MiYu原創(chuàng), 轉帖請注明 : 轉載自 ______________白白の屋
http://www.shnenglu.com/MiYu
Author By : MiYu
Test :
Program :
*/
#include <iostream>
using namespace std;
bool prim[25];
int res[25];
bool hash[25];
int N;
void setPrim ()
{
memset ( prim, 0, sizeof ( prim ) );
prim[2] = prim[3] = prim[5] = prim[7] = prim[11] = prim[13] = prim[17] = prim[19] = prim[23] = true;
}
bool DFS ( int num , int n )
{
res[n] = num;
if ( n > N )
{
return false;
}
if ( n == N - 1 )
{
for ( int i = 2; i <= N; ++ i )
{
if ( prim[num + i] && prim[ i + 1 ] && !hash[i] )
{
res[n+1] = i;
for ( int i = 1; i <= N; ++ i )
printf ( i == 1 ? "%d" : " %d",res[i] );
putchar ( '\n' );
}
}
}
for ( int i = 2; i <= N; ++ i )
{
if ( prim[ num + i ] && !hash[i] )
{
hash[i] = true;
DFS ( i, n + 1 );
hash[i] = false;
}
}
return false;
}
int main ()
{
setPrim ();
int ca = 1;
while ( cin >> N )
{
sizeof ( hash, 0 , sizeof ( hash ) );
printf ( "Case %d:\n",ca++ );
hash[1] = true;
DFS ( 1, 1 );
putchar ( '\n' );
}
return 0;
}