精选文章 dfs学习总结

dfs学习总结

作者:JackZhang861130 时间: 2021-02-07 02:14:55
JackZhang861130 2021-02-07 02:14:55
【摘要】今天做到了dfs的训练,感觉和bfs有相似之处,接下来用一道题来总结一下方法,可类比bfs。 
 上题: 
  
   Description   There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a bl...

今天做到了dfs的训练,感觉和bfs有相似之处,接下来用一道题来总结一下方法,可类比bfs。

上题:

Description

There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can't move on red tiles, he can move only on black tiles. 

Write a program to count the number of black tiles which he can reach by repeating the moves described above. 
 

Input

The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20. 

There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows. 

'.' - a black tile 
'#' - a red tile 
'@' - a man on a black tile(appears exactly once in a data set) 
 

Output

For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself). 
 

Sample Input

 
6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 11 9 .#......... .#.#######. .#.#.....#. .#.#.###.#. .#.#..@#.#. .#.#####.#. .#.......#. .#########. ........... 11 6 ..#..#..#.. ..#..#..#.. ..#..#..### ..#..#..#@. ..#..#..#.. ..#..#..#.. 7 7 ..#.#.. ..#.#.. ###.### ...@... ###.### ..#.#.. ..#.#.. 0 0
 

Sample Output

 
45 59 6 13
 
解题代码:

#include
#include
char point[25][25];
bool flag[25][25]; //flag对应着我们需要研究的点point,用来标记是否曾经到过
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
int count;
void dfs(int x0,int y0,int r,int c)
{ for(int i=0;i<4;i++) for循环用来探索所有邻接点 { int tempx="x0+dx[i],tempy=y0+dy[i];" if(tempx=0&&tempy=0&&flag[tempy][tempx]==false&&point[tempy][tempx]=='.') { count++; flag[tempy][tempx]=true; //满足条件且未标记的标记上 dfs(tempx,tempy,r,c); //通过递归来实现顺藤摸瓜的效果 } } return ;
}
void make_set()
{ for(int i=0;i<25;i++) for(int j="0;j<25;j++)" flag[i][j]="false;" return ; } int main() { c,r,x0,y0; while(1) count="1;" scanf("%d%d",&c,&r); getchar(); if(c="=0&&r==0)" break; i="0;i

与bfs的区别:bfs是通过队列来进行逐层探索,而dfs则是沿着一个路径探索下去一直到底,到底后再返回沿其他路径探索,就和顺藤摸瓜差不多,大体上两者达到的效果基本一致(特殊情况效果有区别),两者均有缺点,bfs在编写代码时较麻烦,用到队列,一般要使用结构体,而dfs则是由于其使用递归调用,大数据易超时。

==================================================================================================================================

赶紧跑回来加一句:最短路径用bfs!!



转载于:https://www.cnblogs.com/ZouCharming/p/3868838.html

勿删,copyright占位
您找到想要的结果了吗?
dfs学习总结
提交成功!非常感谢您的反馈,我们会继续努力做到更好
分享文章到微博
分享文章到朋友圈

上一篇:(转)WITH (NOLOCK)

下一篇:现代软件工程 第十章 【典型用户和场景】 练习与讨论

您可能感兴趣

  • 几个与文本处理相关的Linux命令总结

    1.当前目录下有若干文件,找出扩展名为TextGrid的所有文件,并复制到…/file_set。 find . -name "*.TextGrid" \-exec cp {} ../file_set/ \; ...

  • 【Qt】Qt样式表总结(一):选择器

    官方资料 https://blog.csdn.net/u010168781/article/details/81868523 注释 qss文件中使用:/**/ 来注释 样式规则 样式表由样式规则序列组成。样式...

  • 8-31总结

    jdbk 是数据库连接; 写类的时候必须建包; po包:存放的是javabean类。每个javabean类对应数据库中的一张表,类名和表名一致; dao包:存放的是操作数据的类。即对数据库中的表进行增删查...

  • 大数据是如何实现分析的,该怎样学习

    近几年,互联网行业变化迅速,谈论较多的其中就是“大数据”,大数据岗位炙手可热,薪资拿到手软。但仍有许多童鞋并不了解大数据究竟是什么。 相信很多爱购物的小伙伴们都有一个体会就是,当你逛网站,浏览自己想要买的东西,或者是喜欢的就会在今后推荐你给你相似的,你潜在需要的,其实每个人的淘宝界面都是不一样的,你的淘宝界面上推送的商品,全是你喜欢的或者打算要买的...

  • HDU - 5925 Coconuts 二维坐标离散化,dfs求连通分量

    https://vjudge.net/problem/HDU-5925 /** 题意:一张最大1e9*1e9的图中,最多200个坏点,求连通块个数和大小 思路:二维坐标离散, 将相邻...

  • 6大主流开源SQL引擎总结,遥遥领先的是谁?

    http://36kr.com/p/5072307.html 6大主流开源SQL引擎总结,遥遥领先的是谁? InfoQ技术媒体 • 2017-04-25 • 人工智能 带你来了解主流的开源SQL引擎 编者按:本文来自微信公众号“InfoQ”(ID:infoqchina),作者覃璐,编辑Tina;36氪经授权发布。 根据 O’Reilly 2...

  • 【算法学习】树的重心与点分治

    树的重心 树的重心也叫做树的质心。其本质是一个点,删除这个点后,形成的子树中最大的节点数目最小。 解法 一遍dfs即可。dfs的时候记录一下当前节点 u u ...

  • jQuery的个人总结

    jQuery的个人总结 了解什么是jQuery了解jQuery优点hello jQueryjQuery三种工厂方法jQuery属性写法 jQuery事件写法 jQuery方法写法console.log() 7....

CSDN

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。
dfs学习总结介绍:华为云为您免费提供dfs学习总结在博客、论坛、帮助中心等栏目的相关文章,同时还可以通过 站内搜索 查询更多dfs学习总结的相关内容。| 移动地址: dfs学习总结 | 写博客