UVa 167（八皇后）、POJ2258 The Settlers of Catan——记两个简单回溯搜索-白红宇

UVa 167（八皇后）、POJ2258 The Settlers of Catan——记两个简单回溯搜索

阅读量：6981 次

发布时间：2019-06-27

本文共 1440 字，大约阅读时间需要 4 分钟。

UVa 167

题意：八行八列的棋盘每行每列都要有一个皇后，每个对角线上最多放一个皇后，让你放八个，使摆放位置上的数字加起来最大。

参考：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 int pic[9][9]; 6 int ans; 7 int v[3][20]; 8 void dfs(int cur,int num){ 9     if(cur==8){
   //出现一组解，看能否更新10         ans=max(ans,num);11         return ;12     }13     for(int i=0;i<8;i++){14         if(!v[0][i]&&!v[1][cur+i]&&!v[2][cur-i+8]){
   //v[0] 代表行 v[1]代表副对角线 v[2]代表主对角线15             v[0][i]=1;v[1][cur+i]=1;v[2][cur-i+8]=1;//选这个点，标记16             dfs(cur+1,num+pic[cur][i]);//往下搜索17             v[0][i]=0;v[1][cur+i]=0;v[2][cur-i+8]=0;//复原18         }19     }20 }21 int main(){2223     int n;24     cin>>n;25     while(n--){26         ans=0;27         memset(v,0,sizeof(v));28         for(int i=0;i<8;i++)29             for(int j=0;j<8;j++)30                 cin>>pic[i][j];31         dfs(0,0);32         cout<
        
         <
         
          <

题意：给你点和边的数量，再给你边的连接关系，求最长路径。点可以重复访问，边不行。

参考：

1 #include
     
       2 #include
      
        3 #include
       
         4 #define N 26 5 using namespace std; 6 int n,m,ans; 7 int edg[N][N],vis[N][N]; 8  9 void search(int cur,int len){10     ans=max(ans,len);11     for(int i=0;i
        
         >a>>b;27             edg[a][b]=edg[b][a]=1;//连边28         }29         ans=0;30         for(int i=0;i