深度优先搜索算法(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<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;
}
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;
}
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;
}
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;
}
https://blog.csdn.net/ldx19980108/article/details/76324307#commentBox
文章浏览阅读468次。export NODE_OPTIONS=--openssl-legacy-provider_export n0de_0 ptions=:-openssl-legacy-provider;
文章浏览阅读150次。在上一篇博客iServer GPA模型在实际场景中的使用——实现导入shp数据并切瓦片存储到MongoDB数据库发布服务,我们了解到了在iServer10.2.1版本如何使用GPA处理自动化服务实现相应的功能;随着iServer产品版本的更新,GPA处理自动化服务也升级优化了建模页面UI、模型执行进度信息以及帮助提示等内容;那么接下来我们就使用当前iServer最新版11.1.1a版本的GPA处理自动化服务,为大家演示关于如何实现“将倾斜摄影OSGB数据处理成3DTiles。_gpa模型
文章浏览阅读438次,点赞15次,收藏8次。本系统的功能为科普知识管理、知识分类管理、案例分析管理、用户管理、反馈交流管理、答题管理等。《基于微信小程序ssm的童装商城网站的设计与实现》该项目含有源码、文档等资料、配套开发软件、软件安装教程、项目发布教程等。系统功能完整,适合作为毕业设计、课程设计、数据库大作业 参考 以及学习商用皆可。前端技术:JavaScript、VUE.js(2.X)、css3。开发软件:eclipse/myeclipse/idea。数据库工具:Navicat11。开发语言:Java、小程序。数据库:mysql 5.7。
文章浏览阅读394次,点赞12次,收藏11次。CNN-BIGRU-SAM-Attention多特征分类预测,基于卷积神经网络-双向门控循环单元-空间注意力机制多特征分类预测
文章浏览阅读340次。Problem DescriptionFor he knew every Who down in Whoville beneath, Was busy now, hanging a mistletoe wreath. "And they're hanging their stockings!" he snarled with a sneer, "Tomorrow is Christmas! ..._stockings mom
文章浏览阅读189次。课程回顾:流:转换流:字符和字节的转换对象流(Object):序列化,反序列化打印流(Print):打印各种数据类型的数据今日内容:数据流(Data):支持将基本数据类型写出,字节流,处理流1、DataOutputStream:数据输出字节流常用方法:writeXXX:写出基本数据类型的数据writeUTF:写
文章浏览阅读1.3k次。所 以 对 于 一 维 直 方 图, 我 们 最 好 使 用 这 个函 >数。使 用 np.bincount 时 别 忘 了 设 置 minlength=256。#别忘了中括号 [img],[0],None,[256],[0,256],只有 mask 没有中括号。Numpy 还 有 一 个 函 数 np.bincount(), 它 的 运 行 速 度 是。hist 是一个 256x1 的数组,每一个值代表了与次灰度值对应的像素点数目。#img.ravel() 将图像转成一维数组,这里没有中括号。_pyhon opencv 获取图像直方图
文章浏览阅读86次。项目内容这个作业属于哪个课程2016级计算机科学与工程学院软件工程(西北师范大学)这个作业的要求在哪里实验三 作业互评与改进我们在这个课程的目标是1.学习规范的博文(文档)写作2.理解软件工程各阶段文档的作用与意义,了解软件工程文档的国家标准及其规范任务一:1.2019春季计算机学院软件工程(罗杰)(北京航空航天大学)链接地址:https://www..._软件工程何启芝
文章浏览阅读1.1k次,点赞2次,收藏8次。前言你是否觉得自己从学校毕业的时候只做过小玩具一样的程序?走入职场后哪怕没有什么经验也可以把以下这些课外练习走一遍(朋友的抱怨:学校课程总是从理论出发,作业项目都看不出有什么实际作用,不如从工作中的需求出发)建议:不要乱买书,不要乱追新技术新名词,基础的东西经过很长时间积累而且还会在未来至少10年通用。回顾一下历史,看看历史上时间线上技术的发展,你才能明白明天会是什么样。一_陈浩 coolshell
文章浏览阅读1.4k次,点赞5次,收藏12次。此文章来源于项目官方公众号:“AirtestProject”版权声明:允许转载,但转载必须保留原链接;请勿用作商业或者非法用途前言不知道你有没有遇到这种情况?在刚接触我们的Airtest项目的时候,总是兴致满满、斗志昂扬;但使用一段时间后,却总是被“找不到图片”、“连不上设备”、“录制的脚本不能运行”这些问题劝退。不要着急,今天我们特意跟同学们分享下当年入坑Airtest的经验;希望看完今天这篇攻略,可以让你在入门Airtest的时候少走一些弯路!1.设备连接篇1)连接Android设备A._airtest官网
文章浏览阅读2.8k次。adb 模拟手机操作,获取 微信读书 时长 -> 虚荣心漫番刷广告_adb shell 滑动
文章浏览阅读251次。匠厂出品,必属精品 Uipath中文社区qq交流群:465630324uipath中文交流社区:https://uipathbbs.comRPA之家qq群:465620839第一课--UiPath的安装与激活第二课--UiPath设计器介绍第三课--UiPath变量介绍第四课--UiPath条件判断第五课--UiPath循环第六课--UiPath整合流程控制语句第七课--UiPath邮件发送之..._uipath和python哪个好