Lake Counting
程序员文章站
2022-07-14 21:04:01
...
有一个大小为 N×M的园子,雨后积起了水。八连通的积水被认为是连接在一起的。请求出园子里总共有多少水洼?(八连通指的是下图中相对 W 的*的部分)
***
*W*
***
限制条件
N, M ≤ 100
输入
N=10, M=12
园子如下图(‘W’表示积水,’.'表示没有积水)
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
输出
3
深度优先搜索
从任意的W开始,不停地把邻接的部分用’.‘代替。1次DFS后与初始的这个W连接的所有W就都被替换成了’.’,因此直到图中不再存在W为止,
java实现
import java.util.Scanner;
public class Main {
static char arr[][];
static int sum,N,M;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scn = new Scanner(System.in);
sum=0;
N=scn.nextInt();
M=scn.nextInt();
arr=new char[N][M];
for(int i=0;i<N;i++) {
arr[i]=scn.next().toCharArray();
}
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
if(arr[i][j]=='W') {
f(i,j);
sum++;
}
}
}
System.out.println(sum);
}
private static void f(int i, int j) {
// TODO Auto-generated method stub
for(int a=i-1;a<=i+1;a++) {
for(int b=j-1;b<=j+1;b++) {
if(a<0||b<0||a>=N||b>=M) continue;
if(arr[a][b]=='W') {
arr[a][b]='.';
f(a,b);
}
}
}
}
}
上一篇: ggplot2作图4
下一篇: chapter1 java程序设计基础
推荐阅读
-
Kaby Lake-X怎么样?Kaby Lake-X i7-7740X/i5-7640X深度评测
-
8代酷睿Coffee Lake首测 Intel i5 8250U移动CPU处理器性能对比评测
-
Intel即将揭秘第11代核显:10nm Ice Lake年底见
-
Intel Comet Lake家族酷睿i3-10100桌面处理器现身:首次4核8线程
-
Intel:10nm的Ice Lake处理器相比前代有18% IPC提升
-
Intel退役Kaby Lake-G处理器 A/I合体的杰作消失了
-
10代Ice Lake i7单核性能曝光:同频比Skylake提升40%还多
-
性能提升超乎想象!Intel 10nm Ice Lake与锐龙3000系列处理器单核性能曝光
-
Intel Tiger Lake处理器曝光:集成Gen12显卡、性能给力
-
不是九代胜似九代 Intel Whiskey Lake处理器亮点详细介绍