热门标签 | 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;
}

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


推荐阅读
  • Maven + Spring + MyBatis + MySQL 环境搭建与实例解析
    本文详细介绍如何使用MySQL数据库进行环境搭建,包括创建数据库表并插入示例数据。随后,逐步指导如何配置Maven项目,整合Spring框架与MyBatis,实现高效的数据访问。 ... [详细]
  • 在1995年,Simon Plouffe 发现了一种特殊的求和方法来表示某些常数。两年后,Bailey 和 Borwein 在他们的论文中发表了这一发现,这种方法被命名为 Bailey-Borwein-Plouffe (BBP) 公式。该问题要求计算圆周率 π 的第 n 个十六进制数字。 ... [详细]
  • 本文介绍如何手动实现一个字符串连接函数,该函数不依赖于C语言的标准字符串处理函数,如strcpy或strcat。函数原型为void concatenate(char *dest, char *src),其主要作用是将源字符串src追加到目标字符串dest的末尾。 ... [详细]
  • c语言二元插值,二维线性插值c语言
    c语言二元插值,二维线性插值c语言 ... [详细]
  • 本文将深入探讨 Unreal Engine 4 (UE4) 中的距离场技术,包括其原理、实现细节以及在渲染中的应用。距离场技术在现代游戏引擎中用于提高光照和阴影的效果,尤其是在处理复杂几何形状时。文章将结合具体代码示例,帮助读者更好地理解和应用这一技术。 ... [详细]
  • 根据官方定义,RxJava是一种用于异步编程和可观察数据流的API。其核心特性在于流式处理能力和丰富的操作符支持。 ... [详细]
  • 本文详细介绍了Oracle 11g中的创建表空间的方法,以及如何设置客户端和服务端的基本配置,包括用户管理、环境变量配置等。 ... [详细]
  • publicclassBindActionextendsActionSupport{privateStringproString;privateStringcitString; ... [详细]
  • 本文深入探讨了Go语言中的接口型函数,通过实例分析其灵活性和强大功能,帮助开发者更好地理解和运用这一特性。 ... [详细]
  • 入门指南:使用FastRPC技术连接Qualcomm Hexagon DSP
    本文旨在为初学者提供关于如何使用FastRPC技术连接Qualcomm Hexagon DSP的基础知识。FastRPC技术允许开发者在本地客户端实现远程调用,从而简化Hexagon DSP的开发和调试过程。 ... [详细]
  • 本文探讨了如何通过Service Locator模式来简化和优化在B/S架构中的服务命名访问,特别是对于需要频繁访问的服务,如JNDI和XMLNS。该模式通过缓存机制减少了重复查找的成本,并提供了对多种服务的统一访问接口。 ... [详细]
  • 本文通过分析一个具体的案例,探讨了64位Linux系统对32位应用程序的兼容性问题。案例涉及OpenVPN客户端在64位系统上的异常行为,通过逐步排查和代码测试,最终定位到了与TUN/TAP设备相关的系统调用兼容性问题。 ... [详细]
  • protobuf 使用心得:解析与编码陷阱
    本文记录了一次在广告系统中使用protobuf进行数据交换时遇到的问题及其解决过程。通过这次经历,我们将探讨protobuf的特性和编码机制,帮助开发者避免类似的陷阱。 ... [详细]
  • 嵌套列表的扁平化处理
    本文介绍了一种方法,用于遍历嵌套列表中的每个元素。如果元素是整数,则将其添加到结果数组中;如果元素是一个列表,则递归地遍历这个列表。此方法特别适用于处理复杂数据结构中的嵌套列表。 ... [详细]
  • 本文详细介绍了如何在循环双链表的指定位置插入新元素的方法,包括必要的步骤和代码示例。 ... [详细]
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社区 版权所有