UVa 167（八皇后）、POJ2258 The Settlers of Catan—

UVa 167

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

参考：https://blog.csdn.net/xiaoxiede_wo/article/details/79973171

 #include <iostream>

 #include <cstring>

 #include <iomanip>

 using namespace std;

 int pic[][];

 int ans;

 int v[][];

 void dfs(int cur,int num){

     if(cur==){//出现一组解，看能否更新

         ans=max(ans,num);

         return ;

     }

     for(int i=;i<;i++){

         if(!v[][i]&&!v[][cur+i]&&!v[][cur-i+]){//v[0] 代表行 v[1]代表副对角线 v[2]代表主对角线

             v[][i]=;v[][cur+i]=;v[][cur-i+]=;//选这个点，标记

             dfs(cur+,num+pic[cur][i]);//往下搜索

             v[][i]=;v[][cur+i]=;v[][cur-i+]=;//复原

         }

     }

 }

 int main(){

     int n;

     cin>>n;

     while(n--){

         ans=;

         memset(v,,sizeof(v));

         for(int i=;i<;i++)

             for(int j=;j<;j++)

                 cin>>pic[i][j];

         dfs(,);

         cout<<setw()<<ans<<endl;//输出有个小坑

     }

 }

POJ2258

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

参考：https://blog.csdn.net/miranda_ymz/article/details/79274577

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #define N 26

 using namespace std;

 int n,m,ans;

 int edg[N][N],vis[N][N];

 void search(int cur,int len){

     ans=max(ans,len);

     for(int i=;i<n;i++){

          if(edg[cur][i]==||vis[cur][i]==) continue;//如果两顶点不相连或已访问过，就跳过

         vis[cur][i]=vis[i][cur]=;//选择这个边并继续搜索

         search(i,len+);

         vis[cur][i]=vis[i][cur]=;//复原 回溯

     }

 }

 int main(){

     while(scanf("%d%d",&n,&m)!=EOF&&(n||m)){

          int a,b;

         memset(edg,,sizeof(edg));

         for(int i=;i<m;i++){

             cin>>a>>b;

             edg[a][b]=edg[b][a]=;//连边

         }

         ans=;

         for(int i=;i<n;i++){

             memset(vis,,sizeof(vis));//清空访问

             search(i,);

         }

         cout<<ans<<endl;

     }

     return ;

 }

巴特西

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

最新文章

热门文章