题目链接：UVa 524
题意：
输入正整数n，把正整数1~n组成一个环，使得相邻两个整数之和均为素数。输出时从整数1开始逆时针排列。同一个环应恰好输出一次。n<=16.
分析：
简单BFS.
注意：
- 两测试案例之间有一行空格，输出数据之间有空格，行末无空格
CODE:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;int prime[40] = { 0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1 };
int n, cases = 0, first = 1;struct Node {int a, cnt;int vis[20];int num[20];
}cur,nextnode;void bfs()
{queue<Node> q;memset(cur.vis, 0, sizeof(cur.vis));memset(cur.num, 0, sizeof(cur.num));cur.vis[1] = cur.a = cur.cnt = 1;cur.num[1] = 1;q.push(cur);while (!q.empty()){cur = q.front();q.pop();for (int i = 2; i <= n; i++){if (cur.vis[i] || !prime[cur.a + i]) continue;nextnode.a = i;nextnode.cnt = cur.cnt + 1;for (int j = 1; j <= n; j++){nextnode.vis[j] = cur.vis[j];nextnode.num[j] = cur.num[j];}nextnode.vis[i] = 1;nextnode.num[nextnode.cnt] = i;if (nextnode.cnt == n && prime[nextnode.num[n] + 1]){cout << 1;for (int j = 2; j <= n; j++)cout << " "<< nextnode.num[j] ;putchar('\n');}q.push(nextnode);}}
}int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);
#endifwhile (~scanf("%d",&n)){if (first) first = 0;else printf("\n");printf("Case %d:\n", ++cases);bfs(); }return 0;
}
DFS写法：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <memory>using namespace std;int prime[40]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0};
int vis[20],n,cases=0,a[20];//a[i]=j:素数环第i个位置是j（下标从1开始）void dfs(int x)//处理第x个位置
{if(x-1==n){if(prime[a[n]+1]){for(int i=1;i<=n;i++){if(i==1) printf("%d",a[i]);else printf(" %d",a[i]);}printf("\n");}return ;}else for(int i=2;i<=n;i++){if(!vis[i]&&prime[i+a[x-1]]){vis[i]=1;a[x]=i;dfs(x+1);vis[i]=0;}}
}int main()
{
#ifdef LOCAL//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);
#endifint first=1;while(cin>>n){if(first) first=0;else cout<<endl;printf("Case %d:\n",++cases);a[1]=1;memset(vis,0,sizeof(vis));dfs(2);}return 0;
}