DFS的基础训练清单

2024-05-28 19:38
文章标签 dfs 清单 基础训练

本文主要是介绍DFS的基础训练清单，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

HDU 1010  （AC）

HDU 1015    （AC）

HDU 1016     (AC)

HDU 1172   （AC）

HDU 1312   (AC)

POJ 2362  (AC,1011的弱化版，建议先做这题)

POJ  1011  （AC，强烈推荐）

POJ  3620  

HDU 1010代码

/*******************************************************************************/
/* OS           : 3.2.0-58-generic #88-Ubuntu SMP Tue Dec 3 UTC 2013 GNU/Linux* Compiler     : g++ (GCC)  4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)* Encoding     : UTF8* Date         : 2014-03-24* All Rights Reserved by yaolong.
*****************************************************************************/
/* Description: ***************************************************************
*****************************************************************************/
/* Analysis: ******************************************************************
*****************************************************************************/
/*****************************************************************************/#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;char a[10][10];
int x_d[]={1,-1,0,0};
int y_d[]={0,0,-1,1};int mabs(int i){return i>0?i:-i;}
int m,n,dr_i,dr_j;
int dfs(int x,int y,int t){if(mabs(dr_i-x)+mabs(dr_j-y)>t){return 0;}//奇偶剪枝if(((mabs(x-dr_i)+mabs(y-dr_j))&1)==0&&(t&1)) return 0;if(((mabs(x-dr_i)+mabs(y-dr_j))&1)&&(t&1)==0) return 0;int i,j,k;for(k=0;k<4;k++){i=x+x_d[k];j=y+y_d[k];   //四个方向if(i<0||i>=n||j<0||j>=m) continue ;//保证不越界if(t==1){if(i==dr_i&&j==dr_j) return 1; //到了continue;}if(a[i][j]!='.') continue;a[i][j]='X';if(dfs(i,j,t-1)) return 1;a[i][j]='.';}return 0;}
int main(){#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endifint t;int i,j;int st_i,st_j;while(cin>>n>>m>>t&&(n||m||t)){for(i=0;i<n;i++)for(j=0;j<m;j++){cin>>a[i][j];if(a[i][j]=='S'){st_i=i;st_j=j;}else if(a[i][j]=='D'){dr_i=i;dr_j=j;}}if(mabs(dr_i-st_i)+mabs(dr_j-dr_j)>t){cout<<"NO\n";continue;}if(dfs(st_i,st_j,t)) cout<<"YES\n";else cout<<"NO\n";}#ifndef  ONLINE_JUDGEfclose(stdin);#endifreturn 0;}


1016这题目，我觉得我的做法还是很暴力的，有了1010的基础……没参考任何人，写出来的。没有怎么优化。800MS……的确慢。。不过理解还是很容易的。。n

PE了一次，因为我没看到是每组都输出空行……最后一组测试输出空行就通过了。

/*******************************************************************************/
/* OS           : 3.2.0-58-generic #88-Ubuntu SMP Tue Dec 3 UTC 2013 GNU/Linux* Compiler     : g++ (GCC)  4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)* Encoding     : UTF8* Date         : 2014-03-27* All Rights Reserved by yaolong.
*****************************************************************************/
/* Description: ***************************************************************
*****************************************************************************/
/* Analysis: ******************************************************************
*****************************************************************************/
/*****************************************************************************/#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[][10]={{0},{2,4,6,10,12,16,18},
{1,3,5,9,11,15,17},
{2,4,8,10,14,16},
{1,3,7,9,13,15,19},
{2,6,8,12,14,18},
{1,5,7,11,13,17},
{4,6,10,12,16},
{3,5,9,11,15},
{2,4,8,10,14},
{1,3,7,9,13,19},
{2,6,8,12,18},
{1,5,7,11,17,19},
{4,6,10,16,18},
{3,5,9,15,17},
{2,4,8,14,16},
{1,3,7,13,15},
{2,6,12,14},
{1,5,11,13,19},
{4,10,12,18},
{3,9,11,17}};
int n;
int vist[22],nxt[22];
bool isprime(int k){int t=2;for(;t*t<=k;t++)if(k%t==0) return 0;return 1;}
void dfs(int cur,int nt){int i=0;while(a[cur][i]!=0&&a[cur][i]<=n){if(vist[a[cur][i]]==0){vist[a[cur][i]]=1;nxt[cur]=a[cur][i];if(nt==2&&isprime(a[cur][i]+1)){int p=1;cout<<1;while(nxt[p]!=a[cur][i]){cout<<" "<<nxt[p];p=nxt[p];}cout<<" "<<a[cur][i]<<endl;vist[a[cur][i]]=0;return ;}dfs(a[cur][i],nt-1);vist[a[cur][i]]=0;}i++;}}
int main(){#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endifint cs=0;while(cin>>n){cs++;memset(vist,0,sizeof(vist));vist[1]=1;cout<<"Case "<<cs<<":\n";if(n==1) cout<<1<<endl;else dfs(1,n);cout<<endl;}#ifndef  ONLINE_JUDGEfclose(stdin);#endifreturn 0;}

其实我也不知道1015叫做暴力呢，还是深搜，还是深搜暴力呢。。。

0ms通过，出乎我意料。。。我以为数据会很多。。。

从高位开始枚举，第一个结果输出即可。我用bitmap排了一下序。这么小的数据，用bitmap最合适不过了。。。so easy.1A

/*******************************************************************************/
/* OS           : 3.2.0-58-generic #88-Ubuntu SMP Tue Dec 3 UTC 2013 GNU/Linux* Compiler     : g++ (GCC)  4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)* Encoding     : UTF8* Date         : 2014-03-27* All Rights Reserved by yaolong.
*****************************************************************************/
/* Description: ***************************************************************
*****************************************************************************/
/* Analysis: ******************************************************************
*****************************************************************************/
/*****************************************************************************/#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
using namespace std;
int target;
string psw;
int vist[30];
vector<int> v;
bool isF(int a,int b,int c,int d,int e)
{int dd=d*d;int ee=e*e;//v - w^2 + x^3 - y^4 + z^5 = targetif(a-b*b+c*c*c-dd*dd+ee*ee*e==target){return 1;}return 0;}
void dfs()
{//a - b^2 + c^3 - d^4 + e^5 = targetint a,b,c,d,e;int siz=v.size();int i,j,k,l,m;for(i=0; i<siz; i++){if(vist[i]==-1) continue;a=v[i];vist[i]=-1;for(j=0; j<siz; j++){if(vist[j]==-1) continue;b=v[j];vist[j]=-1;for(k=0; k<siz; k++){if(vist[k]==-1) continue;vist[k]=-1;c=v[k];for(l=0; l<siz; l++){if(vist[l]==-1 ) continue;vist[l]=-1;d=v[l];for(m=0; m<siz; m++){if(vist[m]==-1) continue;vist[m]=-1;e=v[m];if(isF(a,b,c,d,e)){cout<<(char)('A'-1+a)<<(char)('A'-1+b)<<(char)('A'-1+c)<<(char)('A'-1+d)<<(char)('A'-1+e)<<endl;return;}vist[m]=0;  //恢复}vist[l]=0;  //恢复}vist[k]=0;  //恢复}vist[j]=0;  //恢复}vist[i]=0;  //恢复}cout<<"no solution\n";}
int main()
{
#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);
#endifwhile(cin>>target>>psw){memset(vist,0,sizeof(vist));if(target==0&&psw=="END") break;int len=psw.length();for(int i=0; i<len; i++)vist[psw[i]-'A']=1;v.clear();for(int i=25; i>=0; i--)if(vist[i]==1) v.push_back(i+1);dfs();}#ifndef  ONLINE_JUDGEfclose(stdin);
#endifreturn 0;}

HDU1172

/*******************************************************************************/
/* OS           : 3.2.0-58-generic #88-Ubuntu SMP Tue Dec 3 UTC 2013 GNU/Linux* Compiler     : g++ (GCC)  4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)* Encoding     : UTF8* Date         : 2014-04-01* All Rights Reserved by yaolong.
*****************************************************************************/
/* Description: ***************************************************************
*****************************************************************************/
/* Analysis: ******************************************************************
*****************************************************************************/
/*****************************************************************************/#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
class Num{public:Num(){}int nb,n,k;};
int a[4];
int b[4];
int mp1[10];
int mp2[10];bool isLegal(int i,Num N){int j=N.nb,k,cnt=0;for(k=0;k<4;k++){a[k]=i%10;i/=10;b[k]=j%10;j/=10;if(a[k]==b[k]) cnt++;}if(cnt!=N.k){ return 0;}//满足相同的数后memset(mp1,0,sizeof(mp1));memset(mp2,0,sizeof(mp2));cnt=0;for(k=0;k<4;k++){mp1[a[k]]++;mp2[b[k]]++;}for(k=0;k<10;k++){cnt+=min(mp1[k],mp2[k]);}if(cnt!=N.n) return 0;return 1;}
int main(){#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endifint N,i,j;vector<Num> v;int res;while(cin>>N&&N){res=0;v.clear();v.resize(N);for(i=0;i<N;i++){cin>>v[i].nb>>v[i].n>>v[i].k;}for(i=1000;i<10000;i++){for(j=0;j<N;j++){if(!isLegal(i,v[j])){   //满足与否break;}}if(j==N){if(res==0){res=i;}else{res=0;  //第二次赋值，直接break.同时列入not sure状态,我没有用特殊的flag来区分，没必要~break;}}}if(res) cout<<res<<endl;else cout<<"Not sure"<<endl;}#ifndef  ONLINE_JUDGEfclose(stdin);#endifreturn 0;}

这题太暴力了~15MS 水过。。


hdu1312还是水题！

/*******************************************************************************/
/* OS           : 3.2.0-58-generic #88-Ubuntu SMP Tue Dec 3 UTC 2013 GNU/Linux* Compiler     : g++ (GCC)  4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)* Encoding     : UTF8* Date         : 2014-04-13* All Rights Reserved by yaolong.
*****************************************************************************/
/* Description: ***************************************************************
*****************************************************************************/
/* Analysis: ******************************************************************
*****************************************************************************/
/*****************************************************************************/#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char mp[30][30];
bool visit[30][30];
int dfs(int i,int j){int cnt=0;if(mp[i][j]=='.'&&visit[i][j]==0){cnt++;visit[i][j]=1;cnt+=dfs(i+1,j);cnt+=dfs(i,j-1);cnt+=dfs(i-1,j);cnt+=dfs(i,j+1);return cnt;}return cnt;}
int main(){#ifndef ONLINE_JUDGEfreopen("input.txt","r",stdin);#endifint n,m;char c;int st_i,st_j;while(cin>>n>>m&&(n||m)){memset(visit,0,sizeof(visit));memset(mp,'#',sizeof(mp));for(int i=1;i<=m;i++)for(int j=1;j<=n;j++){cin>>c;if(c=='@'){st_i=i;st_j=j;}mp[i][j]=c;}//  cout<<st_i<<" "<<st_j<<endl;int cnt=1;cnt+=dfs(st_i+1,st_j);// cout<<cnt<<"s1"<<endl;cnt+=dfs(st_i,st_j-1);//  cout<<cnt<<"s2"<<endl;cnt+=dfs(st_i-1,st_j);//  cout<<cnt<<"s3"<<endl;cnt+=dfs(st_i,st_j+1);cout<<cnt<<endl;}#ifndef  ONLINE_JUDGEfclose(stdin);#endifreturn 0;}

poj 2362

很好的搜索剪枝！！！

/*******************************************************************************/
/* OS           : 3.2.0-58-generic #88-Ubuntu SMP Tue Dec 3 UTC 2013 GNU/Linux* Compiler     : g++ (GCC)  4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)* Encoding     : UTF8* Date         : 2014-04-13* All Rights Reserved by yaolong.
*****************************************************************************/
/* Description: ***************************************************************
*****************************************************************************/
/* Analysis: ******************************************************************
*****************************************************************************/
/*****************************************************************************/#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int M[25];
bool visit[25];
int edge,n;
bool dfs(int num,int len,int beg){if(num==3){return true;}for(int i=beg;i<=n;i++){if(!visit[i]){visit[i]=1;if(len+M[i]==edge&&dfs(num+1,0,0)){return true; ;}if(len+M[i]<edge&&dfs(num,len+M[i],i+1)){return true;}visit[i]=0;}}return false;}int main(){#ifndef ONLINE_JUDGEfreopen("input.txt","r",stdin);#endifint T;while(cin>>T){while(T--){cin>>n;edge=0;for(int i=1;i<=n;i++){cin>>M[i];edge+=M[i];}if(edge%4!=0){cout<<"no\n";}else{edge>>=2;sort(M+1,M+n+1);if(M[1]==M[n]){if(n%4==0){cout<<"yes\n";}else{cout<<"no\n";}}else{memset(visit,0,sizeof(visit));if(M[n]>edge) cout<<"no\n";else if(dfs(0,0,0)) cout<<"yes\n";else cout<<"no\n";}}/*for(int i=1;i<=n;i++)cout<<M[i]<<endl;*/}}#ifndef  ONLINE_JUDGEfclose(stdin);#endifreturn 0;}


poj 1011

大开眼界的剪枝。

/*******************************************************************************/
/* OS           : 3.2.0-58-generic #88-Ubuntu SMP Tue Dec 3 UTC 2013 GNU/Linux* Compiler     : g++ (GCC)  4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)* Encoding     : UTF8* Date         : 2014-04-13* All Rights Reserved by yaolong.
*****************************************************************************/
/* Description: ***************************************************************
*****************************************************************************/
/* Analysis: ******************************************************************
*****************************************************************************/
/*****************************************************************************/#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int M[80];
bool visit[80];
int edge,n,p,sum;
bool cmp(int a,int b){return a>b;
}
bool dfs(int num,int len,int beg){if(num==p){return true;}int sample=-1;for(int i=beg;i<=n;i++){if(!visit[i]&&M[i]!=sample){visit[i]=1;if(len+M[i]==edge){if(dfs(num+1,0,0))return true; ;sample=M[i];}else if(len+M[i]<edge){if(dfs(num,len+M[i],i+1))return true;sample=M[i];}visit[i]=0;if(len==0) break;}}return false;}
int solve(){for(int len=M[1];len<=sum-len;len++){if(sum%len==0){memset(visit,0,sizeof(visit));p=sum/len;edge=len;// cout<<p<<endl;;if(dfs(0,0,0)){return len;};}}
return sum;}
int main(){#ifndef ONLINE_JUDGEfreopen("input.txt","r",stdin);#endifwhile(cin>>n&&n){sum=0;for(int i=1;i<=n;i++){cin>>M[i];sum+=M[i];}sort(M+1,M+n+1,cmp);// cout<<M[1]<<endl;int ans=solve();cout<<ans<<endl;}/*for(int i=1;i<=n;i++)cout<<M[i]<<endl;*/#ifndef  ONLINE_JUDGEfclose(stdin);#endifreturn 0;}


这篇关于DFS的基础训练清单的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1011499。

相关文章

hdu 2489 (dfs枚举 + prim)

hdu 2489 (dfs枚举 + prim)

题意： 对于一棵顶点和边都有权值的树，使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值，找到一个该图含有m 个顶点的子图，并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析： 因为数据量不大，先用dfs枚举搭配出m个子节点，算出点和，然后套个prim算出边和，每次比较大小即可。 dfs没有写好，A的老泪纵横。 错在把index在d
阅读更多...
poj 3050 dfs + set的妙用

poj 3050 dfs + set的妙用

题意: 给一个5x5的矩阵，求由多少个由连续6个元素组成的不一样的字符的个数。 解析： dfs + set去重搞定。 代码： #include <iostream>#include <cstdio>#include <set>#include <cstdlib>#include <algorithm>#include <cstring>#include <cm
阅读更多...
ural 1149. Sinus Dances dfs

ural 1149. Sinus Dances dfs

1149. Sinus Dances Time limit: 1.0 second Memory limit: 64 MB Let  An = sin(1–sin(2+sin(3–sin(4+…sin( n))…) Let  Sn = (…( A 1+ n) A 2+ n–1) A 3+…+2) An+1 For given  N print  SN Input One
阅读更多...
hdu 6198 dfs枚举找规律+矩阵乘法

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn
阅读更多...
深度优先（DFS）和广度优先（BFS）——算法

深度优先（DFS）和广度优先（BFS）——算法

深度优先 深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支，当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访
阅读更多...
nyoj99（并查集+欧拉路+dfs）

nyoj99（并查集+欧拉路+dfs）

单词拼接 时间限制： 3000 ms  |  内存限制： 65535 KB 难度： 5 描述 给你一些单词，请你判断能否把它们首尾串起来串成一串。 前一个单词的结尾应该与下一个单词的道字母相同。 如 aloha dog arachnid gopher tiger rat   可以拼接成：aloha.arachnid.dog.gopher.rat.tiger 输入 第一行是一个整
阅读更多...
【CF】E. Anya and Cubes（双向DFS）

【CF】E. Anya and Cubes（双向DFS）

根据题意的话每次递归分3种情况 一共最多25个数，时间复杂度为3^25，太大了 我们可以分2次求解第一次求一半的结果，也就是25/2 = 12，记录结果 之后利用剩余的一半求结果 s-结果 = 之前记录过的结果 就可以 时间复杂度降低为 3 ^ (n/2+1) 题目链接：http://codeforces.com/contest/525/problem/E #include<set
阅读更多...
力扣 797. 所有可能路径【DFS】

力扣 797. 所有可能路径【DFS】

1. 题目 2. 代码 DFS ， 直接见代码 class Solution {public:vector<int> path;vector<vector<int>> res; // 结果集void dfs(vector<vector<int>>& graph, int cur, int n){// 找出所有从节点 0 到节点 n-1 的路径// 下标从 0 开始的if (
阅读更多...
CF Bayan 2015 Contest Warm Up B.（dfs+暴力）

CF Bayan 2015 Contest Warm Up B.（dfs+暴力）

B. Strongly Connected City time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接： http://codeforces.com/contest/475/probl
阅读更多...
POJ 2386 Lake Counting（DFS）

POJ 2386 Lake Counting（DFS）

题目： http://poj.org/problem?id=2386 题解： 遍历一次，遇到w，一次DFS后，与此w连接的所有w都被替换成‘ . ’，直到遍历完图中不再存在w为止，总共进行DFS的次数就是答案了。 代码： #include<stdio.h>int N,M;char map[110][110];void dfs(int x,int y){map[x][y]='
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2