本文共 3401 字,大约阅读时间需要 11 分钟。
深度优先搜索算法(Depth First Search,简称DFS):一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件,搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。
回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
int check(参数){ if(满足条件) return 1; return 0;} void dfs(int step){ 判断边界 { 相应操作 } 尝试每一种可能 { 满足check条件 标记 继续下一步dfs(step+1) 恢复初始状态(回溯的时候要用到) }}
1、全排列问题
//全排列问题#include#include int n;char a[15];char re[15];int vis[15];//假设有n个字符要排列,把他们依次放到n个箱子中//先要检查箱子是否为空,手中还有什么字符,把他们放进并标记。//放完一次要恢复初始状态,当到n+1个箱子时,一次排列已经结束void dfs(int step){ int i; if(step==n+1)//判断边界 { for(i=1;i<=n;i++) printf("%c",re[i]); printf("\n"); return ; } for(i=1;i<=n;i++)//遍历每一种情况 { if(vis[i]==0)//check满足 { re[step]=a[i]; vis[i]=1;//标记 dfs(step+1);//继续搜索 vis[i]=0;//恢复初始状态 } } return ;} int main(void){ int T; scanf("%d",&T); getchar(); while(T--) { memset(a,0,sizeof(a)); memset(vis,0,sizeof(vis));//对存数据的数组分别初始化 scanf("%s",a+1); n=strlen(a+1); dfs(1);//从第一个箱子开始 } return 0;}
2、一个环由个圈组成,把自然数1,2,…,N分别放在每一个圆内,数字的在两个相邻圈之和应该是一个素数。 注意:第一圈数应始终为1。
input: N(0~20)
output:输出格式如下所示的样品。每一行表示在环中的一系列圆号码从1开始顺时针和按逆时针方向。编号的顺序必须满足上述要求。打印解决方案的字典顺序。
//Prime Ring Problem//与上面的全排列问题其实思路差不多,只是需要判断的条件比较多//化大为小 #include#include #include int book[25];int result[25];int n;int num;//判断是否为素数int prime(int n){ if(n<=1) return 0; int i; for(i=2;i*i<=n;i++) { if(n%i==0) break; } if(i*i>n) return 1; return 0;}//判断是否能将当前的数字放到当前的圈内int check(int i,int step){ if((book[i]==0) && prime(i+result[step-1])==1) { if(step==n-1) { if(!prime(i+result[0])) return 0; } return 1; } return 0;} void dfs(int step){ if(step==n)//判断边界 { int a; printf("%d",result[0]); for(a=1;a
3、油田问题
问题:GeoSurvComp地质调查公司负责探测地下石油储藏。 GeoSurvComp现在在一块矩形区域探测石油,并把这个大区域分成了很多小块。他们通过专业设备,来分析每个小块中是否蕴藏石油。如果这些蕴藏石油的小方格相邻,那么他们被认为是同一油藏的一部分。在这块矩形区域,可能有很多油藏。你的任务是确定有多少不同的油藏。
input: 输入可能有多个矩形区域(即可能有多组测试)。每个矩形区域的起始行包含m和n,表示行和列的数量,
1<=n,m<=100,如果m =0表示输入的结束,接下来是n行,每行m个字符。每个字符对应一个小方格,并且要么是’*’,代表没有油,要么是’@’,表示有油。
output: 对于每一个矩形区域,输出油藏的数量。两个小方格是相邻的,当且仅当他们水平或者垂直或者对角线相邻(即8个方向)。
//A - Oil Deposits #include#include #include char a[105][105];int n,m,result;int dir[8][2]={ {1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};//表示8个方向 int check(int x,int y)//检查是否有油田{ if(x>=0&&x =0&&y
4、棋盘问题
问题:在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。
input: 输入含有多组测试数据。 每组数据的第一行是两个正整数,n k,用一个空格隔开,表示了将在一个n*n的矩阵内描述棋盘,以及摆放棋子的数目。 n <= 8 , k <= n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状:每行有n个字符,其中 # 表示棋盘区域, . 表示空白区域(数据保证不出现多余的空白行或者空白列)。
output:对于每一组数据,给出一行输出,输出摆放的方案数目C (数据保证C<2^31)。
#include#include #include int n, k, ans;char str[10][10];int vis[100]; void dfs(int r, int k){ if(k==0)//判断边界,此时棋子已经放完 { ans++; return; } for(int i=r; i
转载地址:http://qjrzi.baihongyu.com/