背景描述

ztw同志负责探测地下石油储藏.ztw现在在一块矩形区域探测石油.他通过专业设备,来分析每个小块中是否蕴藏石油.如果这些蕴藏石油的小方格相邻(横向相邻,纵向相邻,还有对角相邻),那么它们被认为是同一油藏的一部分.在这块矩形区域,可能有很多油藏.你的任务是确定有多少不同的油藏.

输入

输入可能有多个矩形区域(即可能有多组测试)。每个矩形区域的起始行包含m和n,表示行和列的数量,1<=n,m<=100,如果m=0表示输入的结束,接下来是n行,每行m个字符.每个字符对应一个小方格,并且要么是‘*’、代表没有油,要么是‘@’,表示有油.(注意多组数据,必要的数组要及时清空~)

输出

对于每一个矩形区域,输出油藏的数量.两个小方格是相邻的,当且仅当他们水平或者垂直或者对角线相邻(即8个方向)。

示例输入

 
1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5 
****@
*@@*@
*@**@
@@@*@
@@**@
0 0 
 

示例输出


0
1
2
2
 
代码:

import java.util.Scanner;

public class Main{
static int n,m,cnt;
static final int N=105;
static char map[][]=new char[N][N];
static int dx[]={0,0,1,-1, 1,-1,1,-1};
static int dy[]={1,-1,0,0,1,-1,-1,1};
static void dfs(int x,int y){
if(map[x][y]=='@'){
map[x][y]='*';
}
for(int i=0;i<8;i++){
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<0 ||yy<0 ||xx>=n ||yy>=m) continue;
if(map[xx][yy]=='*') continue;
dfs(xx,yy);
}
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
while(scan.hasNext()){
n=scan.nextInt();
m=scan.nextInt();
if(n==0 && m==0) break;
for(int i=0;i<n;i++){
map[i]=scan.next().toCharArray();
}
cnt=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(map[i][j]=='@'){
dfs(i,j);
cnt++;
}
System.out.println(cnt);
}
}
}

最新文章

  1. APP都有哪些类型?
  2. SVN 忽略文件但不删除文件
  3. Mysql远程登录授权
  4. centos7安装chrome及加载poatman开发插件
  5. debug连线指令
  6. leetcode_question_85 Largest Rectangle in Histogram
  7. 读懂源码:一步一步实现一个 Vue
  8. How to fix corrupt HDFS FIles
  9. WPF 杂记
  10. 使用 pandas 导出数据
  11. 【评分】Alpha 事后诸葛亮(团队)
  12. Java流程控制练习--万年历
  13. 表单数据转换成json格式数据
  14. iptables只允许指定ip地址访问指定端口
  15. HDU 3507 单调队列 斜率优化
  16. 【树链剖分/倍增模板】【洛谷】3398:仓鼠找sugar
  17. hibernate-笔记
  18. 一个完整的Core Data应用
  19. 《C专家编程》数组和指针并不同--多维数组
  20. Python动态属性和特性(一)

热门文章

  1. vue-socket.io跨域问题的解决方法
  2. react引入ggEditor流程图
  3. 数据库 left()、length()函数
  4. GitHook 工具 —— husky介绍及使用
  5. discuz!ml-3.x版本getshell
  6. 自然语言处理(1)-HMM隐马尔科夫模型基础概念(一)
  7. 09、const与extern在一起跨文件引用
  8. linux下定时网站文件备份和数据备份以及删除旧备份标准代码
  9. node--处理一个增加上传操作和渲染页数条
  10. jquery的封装与对象学习