http://acm.hdu.edu.cn/showproblem.php?pid=1016简单的深搜,要求不重复,设置一个visit数组进行标记,设置result数组进行存储结果。注意dfs后,要重新将visit[i]置0。
#include <iostream>
#include <algorithm>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int result[20];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
bool isprime[]=
{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},visit[20];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void dfs(int step)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i;
if(step==n+1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(isprime[result[n]+1])
for(i=1;i<=n;i++)
printf("%d%c",result[i],i==n?'\n':' ');
return ;
}
for(i=2;i<=n;i++)
if(!visit[i] && isprime[i+result[step-1]])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
result[step]=i;
visit[i]=1;
dfs(step+1);
visit[i]=0;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int count=1;
while(cin>>n)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
memset(visit,0,sizeof(visit));
result[1]=1;
cout<<"Case "<<count++<<":\n";
dfs(2);
cout<<endl;
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted on 2011-04-07 07:04
大大木马 阅读(526)
评论(0) 编辑 收藏 引用