热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

深度优先搜索解题报告:NOJ1102黑白图像问题分析与实现

针对NOJ1102黑白图像问题,本文采用深度优先搜索算法进行详细分析与实现。该问题要求在给定的时间限制(普通Java为1000-3000毫秒)和内存限制(65536KByte)内,处理一个n×n的黑白图像。通过对图像的逐像素遍历,利用深度优先搜索算法有效地识别并标记相连的黑色区域,从而实现图像的高效处理。实验结果显示,该方法在多种测试用例中均能稳定达到预期效果,具有较高的准确性和效率。

黑白图像
时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte
总提交 : 984 测试通过 : 269
比赛描述
输入一个n×n的黑白图像(1表示黑色,0表示白色),任务是统计其中八连块的个数。如果两个黑格子有公共边或者公共顶点,就说它们属于同一个八连块。如下图所示的图形有3个八连块。

输入

第1行输入一个正整数n(n≤700),此后输入n行,每行是由n个0或1组成的字符串。

输出

在输入黑白图像中,八连块的个数

样例输入
6
100100
001010
000000
110000
111000
010100

样例输出
3

这貌似最简单的深搜了,因本人才开始学习,所以参考了学校学长的思路和代码orzorz~~
这里给出学长滴博客地址~~
(http://blog.csdn.net/tc_to_top/article/details/38519551)

我先就我目前的水平谈谈对深搜的看法(大神请无视orzorz!)
在我看来,深搜是对图的遍历的一种方式,代码使用递归实现,但是其思想可以用一颗树来表示,以树最上方的节点开始作为源节点向下搜,当当前节点的所有边都己被探寻过,就回溯到发现节点的那条边的起始节点(也就是递归当前递归到头)。这一过程一直进行到已发现从源节点可达的所有节点为止。一旦发现还存在未被搜索过的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。这就是目前我的理解了。

接下来说说这个题:
1.首先是八连块的理解,以一个块为起点,它的上下左右等八个方向上如果有相同属性的块,那么这些块就是属于同一个八连块了,单独的一个块也单独成块。
2.其次是这个题要求找的是所有的八连块,这里DFS的思路很简单,按着要求写就行。
3.重点来了,就是在输入时如何在外面添加一层保护防止搜索越界,这里我理解了好一阵,感觉确实很精妙,在输入前已经将数组所有元素赋值为0,这时输入就只需要以第二行第二列作为起点,这样直接接形成了一层保护,很舒服的实现!

具体代码如下:

#include 
#include
int const MAX = 702;
int map[MAX][MAX];
int vis[MAX][MAX];

void DFS(int x, int y)
{
//当前为白的或者当前点已访问则返回
if(map[x][y] == 0 || vis[x][y] == 1)
return;
//否则标记当前为已访问
vis[x][y] = 1;
//向八个方向搜索
DFS(x,y-1);
DFS(x,y+1);
DFS(x-1,y);
DFS(x+1,y);
DFS(x-1,y-1);
DFS(x-1,y+1);
DFS(x+1,y-1);
DFS(x+1,y+1);




}

int main()
{
int n, count = 0;
char str[MAX];
scanf("%d",&n);
memset(vis,0,sizeof(vis));
memset(map,0,sizeof(map));
for(int i = 0; i {
scanf("%s", str);
for(int j = 0; j //在图像外面加一圈白,防止DFS越界
map[i+1][j+1] = str[j] - '0';
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
//若找到一个黑的并且其未被访问则开始搜索
if(map[i][j] == 1 && vis[i][j] == 0)
{
DFS(i,j);
count++;
}
printf("%d\n",count);
return 0;
}

欢迎交流!!!
这里写图片描述


推荐阅读
  • 本文作为探讨PHP依赖注入容器系列文章的开篇,将首先通过具体示例详细阐述依赖注入的基本概念及其重要性,为后续深入解析容器的实现奠定基础。 ... [详细]
  • 在处理遗留数据库的映射时,反向工程是一个重要的初始步骤。由于实体模式已经在数据库系统中存在,Hibernate 提供了自动化工具来简化这一过程,帮助开发人员快速生成持久化类和映射文件。通过反向工程,可以显著提高开发效率并减少手动配置的错误。此外,该工具还支持对现有数据库结构进行分析,自动生成符合 Hibernate 规范的配置文件,从而加速项目的启动和开发周期。 ... [详细]
  • 在托管C++中开发应用程序时,遇到了如何声明和操作字符串数组的问题。本文详细探讨了字符串数组在托管C++中的应用与实现方法,包括声明、初始化、遍历和常见操作技巧,为开发者提供了实用的参考和指导。 ... [详细]
  • TypeScript 实战分享:Google 工程师深度解析 TypeScript 开发经验与心得
    TypeScript 实战分享:Google 工程师深度解析 TypeScript 开发经验与心得 ... [详细]
  • 如果程序使用Go语言编写并涉及单向或双向TLS认证,可能会遭受CPU拒绝服务攻击(DoS)。本文深入分析了CVE-2018-16875漏洞,探讨其成因、影响及防范措施,为开发者提供全面的安全指导。 ... [详细]
  • 在2021-2022 ACM集训队月度编程挑战赛第二轮中,题目“最大值与最小值的选择”要求参赛者处理一个包含n个元素的数组,并给定一个整数k。任务是通过选择特定的子数组,计算并返回这些子数组的最大值和最小值之间的差值。该问题考验了选手对数组操作和优化算法的理解与应用能力。 ... [详细]
  • 在牛客2021多校竞赛的一道题目中,涉及了5000×5000×5000的复杂度计算。实验结果显示,使用bitset进行数据处理仅需140毫秒,而使用bool数组则显著较慢。本文通过详细的性能分析,探讨了bitset与bool在数据处理速度上的差异,并提出了针对不同应用场景的优化建议。具体来说,bitset在位级操作上具有更高的效率,适用于大规模数据处理任务,而bool数组则在某些特定场景下更为灵活。通过对这两种数据结构的深入对比,本文旨在为开发者提供选择合适数据结构的参考依据。 ... [详细]
  • 基址获取与驱动开发:内核中提取ntoskrnl模块的基地址方法解析
    基址获取与驱动开发:内核中提取ntoskrnl模块的基地址方法解析 ... [详细]
  • 实现Nginx对ThinkPHP URL重写及PATHINFO支持的详细方法解析【PHP开发】
    在PHP后端开发中,实现Nginx对ThinkPHP的URL重写及PATHINFO支持是一项常见的需求。本文详细解析了经过多次尝试和研究,最终找到的一种有效配置方法,能够确保URL_MODERewrite功能正常运行,并提供稳定的服务。此外,文章还探讨了相关配置项的具体作用及其优化建议,帮助开发者更好地理解和应用这些技术。 ... [详细]
  • 解决CentOS 6.4系统中sda磁盘包含BIOS RAID元数据的问题及专业应对策略
    解决CentOS 6.4系统中sda磁盘包含BIOS RAID元数据的问题及专业应对策略 ... [详细]
  • 在 Windows 10 环境中,通过配置 Visual Studio Code (VSCode) 实现基于 Windows Subsystem for Linux (WSL) 的 C++ 开发,并启用智能代码提示功能。具体步骤包括安装 VSCode 及其相关插件,如 CCIntelliSense、TabNine 和 BracketPairColorizer,确保在 WSL 中顺利进行开发工作。此外,还详细介绍了如何在 Windows 10 中启用和配置 WSL,以实现无缝的跨平台开发体验。 ... [详细]
  • 本文深入探讨了使用Puppet进行软件包分发与管理的方法。首先介绍了fpm这一跨平台的软件包制作工具,其简便的操作流程使得软件包的创建变得轻松快捷。fpm的项目地址为:https://github.com/jordansissel/fpm。通过结合Puppet和fpm,可以实现高效、可靠的软件包管理和部署。 ... [详细]
  • [BZOJ1047] [HAOI2007] 单调队列在理想正方形问题中的应用与优化
    本文探讨了在解决理想正方形问题时,如何利用单调队列进行高效优化。具体而言,给定一个由整数组成的 \(a \times b\) 矩阵,目标是从中找到一个 \(n \times n\) 的子矩阵,使该子矩阵内所有元素的最大值与最小值之差最小。输入部分首先提供三个整数,分别表示矩阵的行数、列数以及子矩阵的边长。通过引入单调队列,算法能够显著提高搜索效率,从而快速找到最优解。 ... [详细]
  • Deepin 20 系统源更换指南及基础设置教程
    配置目标:创建一个适合基本娱乐、办公和直播的环境。安装方法:手动分区。系统要求:EFI分区需大于500MB,根分区建议至少20GB,以确保系统稳定运行和足够的存储空间。此外,建议分配适量的交换分区,以提升系统性能和响应速度。 ... [详细]
  • Java 模式原型在游戏服务器架构中的应用与优化 ... [详细]
author-avatar
书友68610983
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有