题目描述
农夫约翰有一片 N∗M 的矩形土地。
最近,由于降雨的原因,部分土地被水淹没了。
现在用一个字符矩阵来表示他的土地。
每个单元格内,如果包含雨水,则用”W”表示,如果不含雨水,则用”.”表示。
现在,约翰想知道他的土地中形成了多少片池塘。
每组相连的积水单元格集合可以看作是一片池塘。
每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。
请你输出共有多少片池塘,即矩阵中共有多少片相连的”W”块。
输入格式
第一行包含两个整数 N 和 M。
接下来 N 行,每行包含 M 个字符,字符为”W”或”.”,用以表示矩形土地的积水状况,字符之间没有空格。
输出格式
输出一个整数,表示池塘数目。
数据范围
1≤N,M≤1000
输入样例:
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
输出样例:
3
Flood Fill算法
思路:查找每个为M的点进行bfs()搜索并在每次bfs()是进行统计次数的操作,在每一次的bfs()中,当搜索到M的时候将其标记为‘.’
注意:使用 dfs() 会爆Stack Over Flow,所以需要改成bfs()来实现
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
char[][] c = new char[n][m];
for (int i = 0; i < n; i++) {
String next = scan.next();
for (int j = 0; j < next.length(); j++) {
c[i][j] = next.charAt(j);
}
}
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (c[i][j] != '.') {
res++;
bfs(c, i, j);
}
}
}
System.out.println(res);
}
static class Node {
int x = 0;
int y = 0;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void bfs(char[][] c, int x1, int y1) {
Deque<Node> queue = new LinkedList<>();
queue.addLast(new Node(x1, y1));
c[x1][y1] = '.';
while (!queue.isEmpty()) {
Node node = queue.pollFirst();
int x = node.x;
int y = node.y;
for (int i = x - 1; i <= x + 1; i++) {
for (int j = y - 1; j <= y + 1; j++) {
if (i >= 0 && i < c.length && j >= 0 && j < c[0].length && c[i][j] != '.') {
queue.addLast(new Node(i, j));
c[i][j] = '.';
}
}
}
}
}
}