one recursive approach to solve hdu 1016, list all permutations, solve N-Queens puzzle.
reference: the video of stanford cs106b lecture 10 by Julie Zelenski https://www.youtube.com/watch?v=NdF1QDTRkck
// hdu 1016, 795MS
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
const int MAXN=20;
bool isPrime(int k) {
static std::string prime={3,5,7,11,13,17,19,23,29,31,37};
return prime.find(k)!=std::string::npos;
}
void printResult(std::string str) {
static char strbuf[2*MAXN+5], *p;
p=strbuf;
for(auto v:str) { p+=sprintf(p,"%d ",(int)v); }
*--p=0;
puts(strbuf);
}
void recSolvePrimeRing(std::string soFar, std::string rest) {
if(rest.size()==1) {
if(isPrime(rest[0]+soFar.back()) && isPrime(rest[0]+soFar.front()))
printResult(soFar+rest);
return;
}
for(int i=0;i<rest.size();++i) {
int x=rest[i]+soFar.back();
if(isPrime(rest[i]+soFar.back())) {
recSolvePrimeRing(soFar+rest[i],rest.substr(0,i)+rest.substr(i+1));
}
}
}
void solvePrimeRing(int n) {
static std::string rest{'\002'};
if(rest.back()<=n)
for(int i=rest.back()+1;i<=n;++i) rest.push_back(i);
else rest.resize(n-1);
recSolvePrimeRing("\001",rest);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int n,k=0;
while(scanf("%d",&n)==1) {
if(n>0 && n<=MAXN && (n&1)==0) {
printf("Case %d:\n",++k);
solvePrimeRing(n);
putchar('\n');
}
}
return 0;
}// improved version for hdu 1016, 483MS,
// encapsulated to a Solution class, function isprime more speedy,
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
class SolutionPrimeRing {
static const std::string primetable;
static std::string prime;
static inline bool isPrime(int k) {
return (k&1) && prime.find(k)!=std::string::npos;
}
static void printResult(const std::string &str) {
static char strbuf[2*MAXN+5], *p;
p=strbuf;
for(auto v:str) { p+=sprintf(p,"%d ",(int)v); }
*--p=0;
puts(strbuf);
}
static void recSolvePrimeRing(std::string soFar, std::string rest) {
static int tmp;
if(rest.size()==1) {
if(isPrime(rest[0]+soFar.back()) && isPrime(rest[0]+soFar.front()))
printResult(soFar+=rest);
return;
}
for(int i=0;i<rest.size();++i) {
if(isPrime(rest[i]+soFar.back())) {
recSolvePrimeRing(soFar+rest[i],rest.substr(0,i)+rest.substr(i+1));
}
}
}
public:
static const int MAXN=20;
static void solve(int n) {
if(n>MAXN || n<2 || (n&1)) { return; }
static std::string rest{'\002'};
if(rest.back()<=n)
for(int i=rest.back()+1;i<=n;++i) rest.push_back(i);
else rest.resize(n-1);
prime.clear();
n<<=1;
for(int i=0;primetable[i]<n;++i) {
prime.push_back(primetable[i]);
}
recSolvePrimeRing("\001",rest);
}
};
const std::string SolutionPrimeRing::primetable={3,5,7,11,13,17,19,23,29,31,37,41};
std::string SolutionPrimeRing::prime;
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int n,k=0;
while(scanf("%d",&n)==1) {
printf("Case %d:\n",++k);
SolutionPrimeRing::solve(n);
putchar('\n');
}
return 0;
}// Permutation, from the video of stanford cs106b lecture 10 by Julie Zelenski
void RecPermute(string soFar, string rest) {
if(rest=="") {
cout << soFar << endl;
}
else {
for(int i=rest.length()-1;i>=0;--i) {
string next=soFar+rest[i];
string remaining=rest.substr(0,i)+rest.substr(i+1);
RecPermute(next,remaining);
}
}
}
void ListPermutations(string s) {
RecPermute("",s);
}
// 8-Queens, 可以推广到N-queens, limitation, N<=255,(howevev 255 is an astronomical number for N-Queens)
// http://blog.csdn.net/qeatzy/article/details/46811451 contains my C++ code of leetcode N-Queens/N-Queens II in this approach
void printQueenBoard(string str) {
static char line[10]="........";
putchar('[');
for(int i=0, tmp;i<8;++i) {
tmp=str[i]-'0';
line[tmp]='Q';
printf("\"%s\"",line);
line[tmp]='.';
if(i==7) putchar("],\n");
else puts(",");
}
void RecSolveQueen(string soFar, string rest) {
if(rest=="") {
printQueenBoard(soFar);
}
else {
int flag,len;
for(int i=0;i<rest.length();++i) {
flag=1;
len=soFar.length();
for(int j=0;j<len;++j) {
if(rest[i]-soFar[j]==len+i-j || rest[i]-soFar[j]==j-i-len) {
flag==0; break;
}
}
if(flag) {
RecSolveQueen(soFar+rest[i],rest.substr(0,i)+rest.substr(i+1));
}
}
}
}
void eightQueen() {
string s="01234567";
// or string s{'\001','\002',...};
RecSolveQueen("",s);
}版权声明：本文为博主原创文章，未经博主允许不得转载。// p.s. If in any way improment can be achieved, better performance or whatever, it will be well-appreciated to let me know, thanks in advance.