精选文章 dfs学习总结

dfs学习总结

作者:JackZhang861130 时间: 2014-07-19 04:48:00
JackZhang861130 2014-07-19 04:48:00

今天做到了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()
{
    int c,r,x0,y0;
    while(1)
    {
        count=1;
        scanf("%d%d",&c,&r);
        getchar();
        if(c==0&&r==0)
            break;
        for(int i=0;i

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

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

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



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

勿删,copyright占位
分享文章到微博
分享文章到朋友圈

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

下一篇:(转)WITH (NOLOCK)

您可能感兴趣

  • 学习Java开发的人有哪些,Java适合哪类人群学习?

    现在的培训Java怎么样,学习Java开发的人有哪些,Java适合哪类人群学习?提到Java这个名词时,大多数人脑袋中都会浮现出三个字:“程序猿”,从事互联网行业的人群则会浮现出“码农”的字眼。只要是接触过计算机,就不会对这个名词感到陌生,或多或少都有些听闻。不少朋友也对Java挺感兴趣,但都觉得Java需要涉及的知识会非常广,会非常难学,应该只有计算机专业的人才能学得会吧,以自己半路出家的...

  • Elasticsearch 升级 7.x 版本后,我感觉掉坑里了!

    摘要 最近想把我的mall项目升级下,支持SpringBoot 2.3.0 版本。升级过程中发现需要升级Elasticsearch到7.x版本,学习过我的mall项目的朋友应该知道, 我用的Elasticsearch是6.x版本,升级到7.x以后ElasticsearchTemplate都不让用了。本文记录了Elasticsearch从6.x升级到7.x所遇到的一些问题,给大家排排坑! 版本...

  • 【STM32F429开发板用户手册】第38章 STM32F429的FMC总线应用之是32路高速IO扩展

    最新教程下载:http://www.armbbs.cn/forum.php?mod=viewthread&tid=93255 第38章 STM32F429的FMC总线应用之是32路高速IO扩展 本章教程为大家讲解利用STM32429的FMC总线扩展出32路高速IO,且使用简单,实际项目中也比较有实用价值。 目录 第38章 STM32F429的FMC总线应用之是32路高速IO扩展 38.1 初...

  • 【计算机网络】第七章:网络安全

    【计算机网络】第七章:网络安全 目录 网络安全问题概述 1.1.计算机网络面临的安全性威胁 1.2.被动攻击和主动攻击 1.3.计算机网络通信安全的目标 1.4.恶意程序(rogue program) 1.5.计算机网络安全的内容 1.6.一般的数据加密模型 两类密码体制 一、对称密钥密码体制 1.1.对称密钥的缺点与优点 1.2.数据加密标准 DES 1.3.DES 的保密性 二、公钥密码...

  • 五个从存储类内存中受益的应用程序

    存储类内存(SCM)正在迅速摆脱标准技术的炒作周期,进入现实世界。那么有什么好处吗?很简单:突破性的延迟性能。与最新的存储协议NVMe和NVMe-oF结合使用时,系统总响应时间可以缩短一半。 现在,多家供应商在其服务器和存储解决方案中提供了存储类内存(SCM),并且在整个供应商环境中都存在各种实现和支持的可用性模型。服务器通常将单端口存储类内存(SCM)驱动器集成到其系统中,一些存储供应商将...

  • Web端即时通讯实践干货:如何让WebSocket断网重连更快速?

    本文作者网易智慧企业web前端开发工程师马莹莹。为了提升内容质量,收录时有修订和改动。 1、引言 在一个完善的即时通讯IM应用中,WebSocket是极其关键的一环,它为基于Web的即时通讯应用提供了一种全双工的通信机制。但为了提升IM等实际应用场景下的消息即时性和可靠性,我们需要克服WebSocket及其底层依赖的TCP连接对于复杂网络情况下的不稳定性,即时通讯的开发者们通常都需要为其设计...

  • 深入理解卷积神经网络工作原理

    卷积神经网络的核心思想就是设计多个卷积层,卷积层里设计一系列卷积核,输入数据经过卷积层中的卷积核处理,一层层向前推进得到最终的输出数据,这个过程我们称为数据的特征提取。 卷积核 从上面的概述知道,卷积核是卷积神经网络的核心,这也是它为什么叫卷积神经网络的原因。那么要理解卷积神经网络的原理,就必须理解卷积核,而要理解卷积核,要从图像处理开始理解。 上图可以大致表示图像处理的原理:利用一定大小的...

  • 怎样学习Python

    在了解了Python的优势、应用、就业前景以及其不可替代的价值之后,相信大家都会有学习python的冲动。那应该如何学习Python呢?买一本书、找一套视频、报名一个培训班?从理论上来讲,无论选择哪种学习方式,都可以掌握Python语言,但实际情况而言,总会因为某些原因导致自己的学习计划搁浅。所以在这里整理本片文章,希望本文能为大家的学习节约更多的时间成本。 1、找到自己学习Python的初...

华为云40多款云服务产品0元试用活动

免费套餐,马上领取!
CSDN

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。