- 1centos开机自启的方式总结
- 2video-player的使用
- 3STC89C52单片机 启动！！！（一）
- 4Python第一周学习笔记_绘制多个起点相同但大小不同的五角星
- 5unbuntu里面没有ip_抖音怎么打造个人ip，如何打造抖音个人IP
- 6Ubuntu下Hadoop的安装教程_ubuntu安装hadoop教程
- 7Unity 使用Pico的SDK进行开发_picomobilesdk
- 8HarmonyOS NEXT应用开发之ArkWeb同层渲染_nodecontainer nodecontroller
- 9javaweb-实验九-复盘_javaweb实验
- 10《python数据分析与挖掘实战》笔记第5章_数据分析与挖掘实战第五章代码
C语言 DFS(深度优先搜索算法) 详解_c语言dfs
赞
踩
基本概念
深度优先搜索算法（Depth First Search，简称DFS）：一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。
算法思想
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
基本模板
int check(参数) { if(满足条件) return 1; return 0; } void dfs(int step) { 判断边界 { 相应操作 } 尝试每一种可能 { 满足check条件 标记 继续下一步dfs(step+1) 恢复初始状态（回溯的时候要用到） } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
问题示例
1、全排列问题
//全排列问题 #include<stdio.h> #include<string.h> 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; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
2、一个环由个圈组成，把自然数1，2，…，N分别放在每一个圆内，数字的在两个相邻圈之和应该是一个素数。 注意：第一圈数应始终为1。
input: N(0~20)
output:输出格式如下所示的样品。每一行表示在环中的一系列圆号码从1开始顺时针和按逆时针方向。编号的顺序必须满足上述要求。打印解决方案的字典顺序。
//Prime Ring Problem //与上面的全排列问题其实思路差不多，只是需要判断的条件比较多 //化大为小 #include<stdio.h> #include<string.h> #include<stdlib.h> 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<n;a++) { printf(" %d",result[a]); } printf("\n"); return ; } int i; for(i=2;i<=n;i++)//遍历每一种情况 { if(check(i,step))//check是否满足 { book[i]=1;//标记 result[step]=i;//记录结果 dfs(step+1);//继续往下搜索 book[i]=0;//恢复初始状态 } } } int main(void) { while(scanf("%d",&n)!=EOF) { num++; memset(result,0,sizeof(result)); memset(book,0,sizeof(book)); result[0]=1; printf("Case %d:\n",num);//格式比较容易出错 dfs(1); printf("\n"); } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
3、油田问题
问题：GeoSurvComp地质调查公司负责探测地下石油储藏。 GeoSurvComp现在在一块矩形区域探测石油，并把这个大区域分成了很多小块。他们通过专业设备，来分析每个小块中是否蕴藏石油。如果这些蕴藏石油的小方格相邻，那么他们被认为是同一油藏的一部分。在这块矩形区域，可能有很多油藏。你的任务是确定有多少不同的油藏。
input: 输入可能有多个矩形区域（即可能有多组测试）。每个矩形区域的起始行包含m和n，表示行和列的数量，
1<=n,m<=100，如果m =0表示输入的结束，接下来是n行，每行m个字符。每个字符对应一个小方格，并且要么是’*’，代表没有油，要么是’@’，表示有油。
output: 对于每一个矩形区域，输出油藏的数量。两个小方格是相邻的，当且仅当他们水平或者垂直或者对角线相邻（即8个方向）。
//A - Oil Deposits #include<stdio.h> #include<string.h> #include<stdlib.h> 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<m&&y>=0&&y<n&&a[x][y]=='@') return 1; return 0; } int dfs(int x, int y) { int i,xx,yy; if(check(x,y)) { a[x][y]='.'; //统计之后就可以把该油田标记，且不用恢复（要不会重复）， //也可以用一个数组来存每个点的访问情况，但是感觉没必要，浪费空间 for(i=0;i<8;i++) { xx=x+dir[i][0]; yy=y+dir[i][1]; dfs(xx,yy);//依次检查8个方向 } return 1; } return 0; } int main(void) { int i,j; while(scanf("%d %d",&m,&n)==2) { if(m==0&&n==0) break; result = 0; memset(a,0,sizeof(a)); for(i=0;i<m;i++) scanf("%s",a[i]); for(i=0;i<m;i++)//在每一个点都搜索一次 { for(j=0;j<n;j++) { if(dfs(i,j))//找到油田就可以将结果加1 result++; } } printf("%d\n",result); } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
4、棋盘问题
问题：在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
input： 输入含有多组测试数据。 每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
output：对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
#include<stdio.h> #include<string.h> #include<stdlib.h> 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<n; i++)//每次都从放过棋子下一行开始搜索，保证不重复 { for(int j=0; j<n; j++) { //循环保证行不重复，check保证列不重复 if(str[i][j]=='.' || vis[j]==1) continue;//不满足条件直接跳过 vis[j] = 1;//标记 dfs(i+1, k-1);//继续下一次标记 vis[j] = 0;//恢复初始状态 } } } int main(void) { while(1) { scanf("%d %d", &n, &k); getchar(); if(n==-1 && k==-1) break; memset(str, '\0', sizeof(str)); memset(vis, 0, sizeof(vis)); ans = 0; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) str[i][j] = getchar(); getchar(); } dfs(0, k);//从第0行开始放，此时手中还剩k个棋子 printf("%d\n", ans); } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
