题目描述

农夫约翰有一片 N∗M 的矩形土地。

最近，由于降雨的原因，部分土地被水淹没了。

现在用一个字符矩阵来表示他的土地。

每个单元格内，如果包含雨水，则用”W”表示，如果不含雨水，则用”.”表示。

现在，约翰想知道他的土地中形成了多少片池塘。

每组相连的积水单元格集合可以看作是一片池塘。

每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。

请你输出共有多少片池塘，即矩阵中共有多少片相连的”W”块。

样例

输入样例：
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

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1010;
char g[N][N];
int n, m;
int dist[N][N];//判重数组，记录最短距离数组
int dx[] = {1, -1, 0, 0, -1, -1, 1, 1}, dy[] = {0, 0, 1, -1, 1, -1, 1, -1};//偏移量
int res;
void bfs(int x, int y)
{
    queue<pair<int,int>> q;
    q.push({x, y});
    dist[x][y] = 0;
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 8; i ++ )
        {
            int nx = t.first + dx[i], ny = t.second + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (g[nx][ny] == '.') continue;
            if (dist[nx][ny] != -1) continue;
            dist[nx][ny] = dist[t.first][t.second] + 1;
            q.push({nx, ny});
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 0; i < n; i ++ ) scanf("%s", &g[i]);
    memset(dist, -1, sizeof(dist));
    for (int i= 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if (g[i][j] == 'W' && dist[i][j] == -1)
            {
                bfs(i, j);
                res ++ ;
            }

    cout << res << endl;
    return 0;
}