HDU1241 Oil Deposits(dfs+连通块问题)
2024-10-08 10:14:40
背景描述
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);
}
}
}
最新文章
- APP都有哪些类型?
- SVN 忽略文件但不删除文件
- Mysql远程登录授权
- centos7安装chrome及加载poatman开发插件
- debug连线指令
- leetcode_question_85 Largest Rectangle in Histogram
- 读懂源码:一步一步实现一个 Vue
- How to fix corrupt HDFS FIles
- WPF 杂记
- 使用 pandas 导出数据
- 【评分】Alpha 事后诸葛亮(团队)
- Java流程控制练习--万年历
- 表单数据转换成json格式数据
- iptables只允许指定ip地址访问指定端口
- HDU 3507 单调队列 斜率优化
- 【树链剖分/倍增模板】【洛谷】3398:仓鼠找sugar
- hibernate-笔记
- 一个完整的Core Data应用
- 《C专家编程》数组和指针并不同--多维数组
- Python动态属性和特性(一)