奋战杭电ACM（DAY11）1016

本文主要是介绍奋战杭电ACM（DAY11）1016，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

DFS加回溯

具体见注释

Prime Ring Problem

#include <iostream>
using namespace std;int n,circle[20],p[20];
bool visited[20];
int prime[]={1,3,5,7,11,13,17,19,23,29,31,37};//建立素数表，避免每次判断，减少时耗void print(int x)
{for(int i=1; i<x; i++)cout << circle[i] << " ";cout << circle[x] << endl;//最后一个数后面没有空格，PE一次……
}bool ifprime ( int y)
{for(int i=0; i<12; i++){if(y==prime[i])return true;}return false;
}void dfs(int t)
{if(t>n) {print(n);return;}for(int i=2; i<=n; i++){if(visited[i]==true) continue;visited[i]=true;circle[t]=p[i];if(t==n){if(ifprime(circle[t]+circle[t-1]) && ifprime(circle[t]+1))dfs(t+1);}else{if(ifprime(circle[t]+circle[t-1])) dfs(t+1);}visited[i]=false;}
}int main()
{int num =0;while(cin >> n){	num +=1;memset(circle,0,sizeof(circle));memset(visited,false,sizeof(visited));for(int i=0; i<20; i++)p[i]=i;circle[1]=1;visited[1]=true;cout << "Case " << num << ":" << endl;dfs(2);cout << endl;}return 0;
}

这篇关于奋战杭电ACM（DAY11）1016的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---