Oil Deposits
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3087 Accepted Submission(s): 1765
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
说到深搜,就是所谓的dfs,我首先就是想到这一题,因为我做的第一道深搜题就是这一道,给我非常大的启发,原来深搜(dfs)就是如此!!!
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1241
我的代码:
//Oil Deposits
#include <iostream>
#include <stdio.h>
using namespace std;
char map[101][101];
int n, m, sum;
void dfs(int i, int j)
{
//若该点不可行或越界,返回
if(map[i][j]!='@' || i<0 || j<0 || i>=m || j>=n) return;
else //否则,标记该点为不可行,再往8个方向深搜
{
map[i][j] = '!';
dfs(i-1, j-1);
dfs(i-1, j);
dfs(i-1, j+1);
dfs(i, j-1);
dfs(i, j+1);
dfs(i+1, j-1);
dfs(i+1, j);
dfs(i+1, j+1);
}
}
int main()
{
int i, j;
while(cin>>m>>n)
{
if(m==0 || n==0) break;
sum = 0;
for(i = 0; i < m; i++)
for(j = 0; j < n; j++)
cin>>map[i][j];
for(i = 0; i < m; i++)
{
for(j = 0; j < n; j++)
{
if(map[i][j] == '@')
{
dfs(i, j);
sum++;
}
}
}
cout<<sum<<endl;
}
return 0;
}
分享到:
相关推荐
### 知识点解析 #### 一、题目背景与理解 根据给定的文件信息,我们可以得知这是一段用于解决HDU(Hdu Online Judge)编号为...综上所述,这段代码有效地解决了HDU 1241的问题,展示了DFS在解决实际问题中的应用。
"HDU1241 Oil Deposits.cpp"很可能就是通过BFS策略,解决了资源分配或路径规划的问题。 在这些题目中,"HDU1242 Rescue.cpp"可能涉及到对图的深度优先搜索,模拟救援任务的执行顺序;"HDU1240 Asteroids!".cpp可能...
HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
8. **图论与树**:HDU题目中可能涉及图的遍历(深度优先搜索DFS、广度优先搜索BFS)、树的遍历(前序、中序、后序)以及最小生成树、最短路径等算法。 9. **动态规划**:这是一种优化策略,通过构建状态转移方程来...
"HDU最全ac代码"这个压缩包很可能是包含了在HDU平台上解题通过的完整源代码集合,旨在帮助学习者理解和掌握各种算法,提升编程解决问题的能力。 首先,我们来了解一下ACM/ICPC比赛。这是一项全球性的编程竞赛,参赛...
### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...
HDU图论题目分类 HDU图论题目分类是指在杭州电子科技大学(Hangzhou Dianzi University)的判题平台HDU OJ(Online Judge)上收录的一系列图论题目的分类。本分类涵盖了图论领域的多种类型的题目,涉及到图论的基本...
【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...
HDU1059的代码
hdu1001解题报告
HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...
hdu 1574 passed sorce
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...
八数码的A*算法~不是很高效,但是很适合刚刚学这个算法的朋友们
HDU ACM教案是针对ACM/ICPC(国际大学生程序设计竞赛)的训练教程,旨在帮助参赛者提升算法和编程技能。"搜索入门"这部分内容是教程中的一个重要章节,主要介绍在解决算法问题时如何有效地运用搜索策略。在这个章节...
hdu2101AC代码
【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...