HDU 1241 Oil Deposits(八连块问题) 与 黑白图像(刘汝佳的小白6.4.1)同样的原理(DFS)
AC代码:
发布日期:2021-11-06 16:56:41
浏览次数:3
分类:技术文章
本文共 1977 字,大约阅读时间需要 6 分钟。
Oil Deposits
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 11377 Accepted Submission(s): 6638 Problem Description
The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.
Input
The input file contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 <= m <= 100 and 1 <= n <= 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either `*', representing the absence of oil, or `@', representing an oil pocket.
Output
For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.
Sample Input
1 1*3 5*@*@***@***@*@*1 8@@****@*5 5 ****@*@@*@*@**@@@@*@@@**@0 0
Sample Output
0122
#include#include char a[110][110];int vis[110][110],m,n;//author:XXYYvoid dfs(int x,int y){ if(vis[x][y]||a[x][y]=='*'||x<0||y<0||x==m||y==n) return; vis[x][y]=1; dfs(x-1,y-1);dfs(x-1,y);dfs(x-1,y+1); dfs(x,y-1);dfs(x,y+1); dfs(x+1,y-1);dfs(x+1,y);dfs(x+1,y+1);}int main(){ int i,j,ans; while(~scanf("%d%d",&m,&n),(m+n)){ memset(vis,0,sizeof(vis)); for(i=0;i
转载地址:https://blog.csdn.net/YJX_xx/article/details/37658229 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年04月25日 01时15分49秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
【CSDN2012年度博客之星】需要您的一票,感谢大家的支持
2019-04-27
PHP对于浮点型的数据需要用不同的方法去解决
2019-04-27
Tokyo Cabinet 安装
2019-04-27
Flink在美团的应用与实践听课笔记
2019-04-27
Java多线程的11种创建方式以及纠正网上流传很久的一个谬误
2019-04-27
JDK源码研究Jstack,JMap,threaddump,dumpheap的原理
2019-04-27
Java使用字节码和汇编语言同步分析volatile,synchronized的底层实现
2019-04-27
javac编译原理和javac命令行的使用
2019-04-27
Unity使用UnityWebRequest实现本地日志上传到web服务器
2019-04-27
Unity使用RenderTexture实现裁切3D模型
2019-04-27
美术和程序吵架,原来是资源序列化格式设置不统一
2019-04-27
Unity iOS接SDK,定制UnityAppController
2019-04-27
Unity iOS接SDK前先要了解的知识(Objective-C)
2019-04-27
记一次iOS闪退问题的定位:NSLog闪退
2019-04-27
Unity打开照相机与打开本地相册然后在Unity中显示照片(Android与iOS)
2019-04-27
无需接入SDK即可在Unity中获取经纬度(Android/iOS),告诉我你的坐标
2019-04-27
Unity获取系统信息SystemInfo(CPU、显卡、操作系统等信息)
2019-04-27
Unity中获取物体的尺寸(size)的三种方法
2019-04-27
Unity中的关节组件和绳子效果的实现
2019-04-27