总结一下实现dfs搜索时出现的小问题
发布日期:2021-06-29 11:10:22
浏览次数:3
分类:技术文章
本文共 1129 字,大约阅读时间需要 3 分钟。
1;每次路径搜索要注意是否要进行变化和[还原(回溯)]=有必要的时候才会有回溯;
例如hdu1010题;判断t时刻是否可以从S到达D处;这里就要每次这个路径结束时要还原;也就是回溯;看代码实现;for(i=0;i<4;i++) { int fx=x+dir[i][0]; int fy=y+dir[i][1]; if(fx>=0&&fx=0&&fy
看那两个map赋值就是完成这一步骤;实现变化和还原;
这一步骤就是实现了已fx,fy为中心往四周进行搜索的目的;2;控制搜索的方向;就是用数组加上for循环来实现的;
看代码; 这是8方的搜索;要定义【8】【2】的数组;for(i = 0; i < 8; i++)来实现的; 4面也是同样的;int fs[8][2]={ {1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,1},{1,-1},{-1,-1}};void dfs(int x,int y){ int i,fx,fy; for(i = 0; i < 8; i++){ fx = x + fs[i][0]; fy = y + fs[i][1]; if(fx>=0&&fx =0&&fy
3;进入递归的那个if判断,一定要注意其边界条件;要控制在矩阵内部;
代码;if(fx>=0&&fx =0&&fy
4;读入字符的时候尽量使用%s进行读入;还要注意与之前的横列别搞错了。
for(i = 0; i < a; i++){ scanf("%s",map1[i]); }
5;这也是最重要最灵活的一点;
根据题目要求; 在合适的地方插入判断或者变量进行计数判断;实现相应的目的。 hdu1241就是在主函数那插入num++;进行计数for(i = 0; i < a; i++){ for(j = 0; j < b; j++){ if(map1[i][j]=='@'){ map1[i][j]='*'; num++; dfs(i, j); } } }
hdu1010的迷宫类型的题;
问t时刻是否可以到达D处; 就是利用插入if的判断实现目的的;这些判断也叫做剪枝了;转载地址:https://blog.csdn.net/zw1996/article/details/51906946 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
初次前来,多多关照!
[***.217.46.12]2024年04月22日 18时46分22秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
STM32Cube_FW_F4_V1.17 F4固件包百度网盘下载
2019-04-29
猿来绘Java-35-线程的同步(生产者和消费者问题)
2019-04-29
猿来绘Java-36-解决线程安全问题
2019-04-29
猿来绘Java-37-ReentrantLock解决线程安全问题
2019-04-29
猿来绘Java-38-生产者消费者模型
2019-04-29
猿来绘Java-39-JDK8的新日期时间类
2019-04-29
猿来绘Java-40-比较器(Comparable 接口与 CompareTo方法)
2019-04-29
猿来绘Java-41-源码分析String对象的数组的排序(JDK1.8)
2019-04-29
猿来绘Java-42-枚举类的使用
2019-04-29
猿来绘Java-43-初步认识注解
2019-04-29
猿来绘Java-44-自定义注解和元注解
2019-04-29
猿来绘Java-45-JDK8新特性可重复注解和类型注解
2019-04-29
猿来绘Java-46-Collection接口及其方法
2019-04-29
猿来绘Java-47- foreatch 增强for循环
2019-04-29
2021/4/27课堂总结和作业
2019-04-29
2021.4.28课堂总结和作业
2019-04-29
2021.4.29课堂总结
2019-04-29
2021.4.30课堂总结和作业
2019-04-29
需要吗?2000GB+学习视频教程 面试资料免费下载
2019-04-29
MySQL对已存在数据库表添加自增ID字段
2019-04-29