acwing1097. 池塘计数（bfs）

农夫约翰有一片 N∗MN∗M 的矩形土地。
最近，由于降雨的原因，部分土地被水淹没了。
现在用一个字符矩阵来表示他的土地。
每个单元格内，如果包含雨水，则用”W”表示，如果不含雨水，则用”.”表示。
现在，约翰想知道他的土地中形成了多少片池塘。
每组相连的积水单元格集合可以看作是一片池塘。
每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。
请你输出共有多少片池塘，即矩阵中共有多少片相连的”W”块。

输入格式

第一行包含两个整数 NN 和 MM。
接下来 NN 行，每行包含 MM 个字符，字符为”W”或”.”，用以表示矩形土地的积水状况，字符之间没有空格。

输出格式

输出一个整数，表示池塘数目。

数据范围

1≤N,M≤10001≤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

import java.util.*;
import java.io.*;
public class Main {
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.             in));
    static int n,m;
    static char[][] arr;
    private static void bfs (int sx, int sy) {
        Deque<int[]> queue = new ArrayDeque<>();
        queue.addFirst(new int[]{sx,sy});
        while (!queue.isEmpty()) {
            int[] t = queue.pollFirst();
            int x = t[0], y = t[1];
            for (int i = x-1; i <= x+1; ++i) 
                for (int j = y-1; j <= y+1; ++j) {
                    if (i < 0 || i > n-1 || j < 0 || j > m-1) continue;
                    if (i == sx && j == sy) continue;
                    if (arr[i][j] == '.') continue;
                    queue.addFirst(new int[]{i,j});
                    arr[i][j] = '.';
                }
        }
    }
    public static void main(String args[]) throws IOException {
        String[] s = cin.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        arr = new char[n][m];
        for (int i = 0; i < n; ++i) {
            String str = cin.readLine();
            for (int j = 0; j < m; ++j) 
                arr[i][j] = str.charAt(j);
        }
        int res = 0;
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < m; ++j) 
                if (arr[i][j] == 'W') {
                    bfs(i,j);
                    res++;
                }
        System.out.println(res);
    }
}