Oil Deposits

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 16542    Accepted Submission(s):
9500

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
0
1
2
2
 
简单的搜索题  和南阳的 水池数目差不多  只不过增加了 四个方向的搜索
/*
题意:给你一个规格为n*m的矩阵,由
字符'@'和'*'组成,问所有的@组成的区域
有多少块,(@组成的区域指向它的八个方向中其中一个方向
走依然是@)
题解:先找到第一个@,然后向这个@的八个方向查找,将所有查找到的
@都替换为*(将找过的位置覆盖,避免重复查找),看最后调用了dfs函数
多少次,就有多少个区域
*/ #include<stdio.h> ///hdu1241
#include<string.h>
#include<algorithm>
#define MAX 110
#define INF 0x3f3f3f
char map[MAX][MAX];
int n,m;
void dfs(int x,int y)
{
int i,j;
int move[8][2]={1,0,-1,0,0,1,0,-1,1,-1,1,1,-1,1,-1,-1};
if(map[x][y]=='@'&&0<=x&&x<n&&0<=y&&y<m)
{
map[x][y]='*';
for(i=0;i<8;i++)//搜索八个方向
dfs(x+move[i][0],y+move[i][1]);
//可以用上边的辅助数组进行搜索 ,也可以直接按照下边注释的
//方法搜索,其原理相同
// dfs(x-1,y);
// dfs(x+1,y);
// dfs(x,y-1);
// dfs(x,y+1);
// dfs(x-1,y-1);
// dfs(x-1,y+1);
// dfs(x+1,y-1);
// dfs(x+1,y+1);
}
return ;
}
int main()
{
int j,i,t,k;
while(scanf("%d%d",&n,&m),n|m)
{
for(i=0;i<n;i++)
scanf("%s",map[i]); int sum=0;
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(map[i][j]=='@')
{
dfs(i,j);
sum++;
}
}
}
printf("%d\n",sum);
}
return 0;
}

  

  

最新文章

  1. Hibernate中使用Criteria查询
  2. 剑指Offer面试题:13.调整数组顺序使奇数位于偶数前面
  3. javax.crypto.BadPaddingException: Given final block not properly padded 解决方法
  4. 未注册wang域名批量查询工具
  5. sqlserver 跨服务器访问数据
  6. c++find函数用法
  7. 在 Perl 中使用 Getopt::Long 模块来接收用户命令行参数
  8. RMAN 完全恢复
  9. backbone todo example
  10. rsync与inotify 数据同步
  11. for计算100以内的奇数和
  12. Linux 进程状态 概念 Process State Definition
  13. dedecms利用memberlist标签调用自定义会员模型的会员信息
  14. oracle删除某个用户所有表(转)
  15. Postman-----Response body:JSON value check的使用介绍
  16. Rank of Tetris 拓扑排序+并查集
  17. 潜在风险的频次vs潜在风险的严重影响的程度(以及恢复)
  18. 读书笔记——《You Don&#39;t Know JS》
  19. ENQUIRE the predecessor to the World Wide Web.
  20. cm5.9.2安装spark启动报错解决办法

热门文章

  1. JavaScript函数调用
  2. MySql排序性能对比
  3. Command-line tools can be 235x faster than your Hadoop cluster
  4. WAF 与 RASP 的安装使用大比拼!
  5. PHP reset() 函数
  6. 环信_EaseUI 使用指南
  7. [Unity菜鸟] Mecanim 系统遇到的问题
  8. 【HDOJ】1016 Prime Ring Problem
  9. 【Pyhton Network】使用poll()或select()实现非阻塞传输
  10. 应付期间 Payables Periods