随笔 - 19, 文章 - 0, 评论 - 2, 引用 - 0
数据加载中……

hdu1016_Prime Ring Problem

        简单而且经典的搜索题,用回溯做。对于什么是回溯什么是DFS我分不清。就是按位逐个判断,直到找到结果,或者出界退出。

#include<iostream>
#include
<cmath>
using namespace std ;
int n, a[111], k, ans[22], anscnt ;
int p[42]= {0,0,2,3,0,5,0,7,0,0,0,11,0,13,0,0,0,17,0,19,0,
           
0,0,23,0,0,0,0,0,29,0,31,0,0,0,0,0,37,0,0,0,41}
 ;

int rev[100][20], revcnt ;

void DFS( int m, int geshu )
{
    
int i, j ;
    
if( geshu == n && p[1+m] ){
        cout 
<< ans[0] ;
        
for( i=1; i<n; ++i ){
            cout 
<< " " << ans[i] ;
            rev[revcnt][i] 
= ans[i] ;
        }

        
++revcnt ;
        cout 
<< "\n" ;
    }

    
else if( geshu == n )
        
return ;
    
for( j=2; j<=n; ++j ){
        
if( j<p[j+m] && !a[j] ){
            a[j] 
= 1 ;
            ans[geshu] 
= j ;
            DFS( j, geshu
+1 ) ;
            a[j] 
= 0 ;
        }

    }

}


int main( )
{
    
int i, j ;
    
for( j=1; cin >> n; ++j ){
        cout 
<< "Case "<< j << ":\n" ;
        
for( i=0; i<111++i )
            a[i] 
= 0 ;
        revcnt 
= 0 ;
        k 
= 1 ;
        ans[
0= 1 ;
        anscnt 
= 1 ;
        DFS( 
11 ) ;
        cout 
<< "\n";
    }

    
return 0 ;
}

posted on 2009-06-05 10:55 祝你好运! 阅读(181) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理