题目描述

农夫约翰有一片 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

时间限制

1s

空间限制

64MB

算法1

(Flood_Fill)

Flood_Fill，顾名思义，洪水覆盖法。
我们每次把经过遍历的点看作已经被覆盖的点。
每次向八个方向扩展即可。
这里不多说，以后会抽时间写一个分享。

时间复杂度

线性。

C++ 代码

#include<bits/stdc++.h>
//传说中的万能头文件
using namespace std;
const int N = 1010;
int n, m;
char g[N][N];
//表示整个地图
pair<int, int> q[N * N];
//bfs中的队列
bool st[N][N];
//判重数组
void Flood_Fill(int x, int y)
{
    int hh = 0, tt = -1;//定义队头队尾

    q[ ++ tt] = {x, y};//把这个要搜的点先放到队列和st判重数组里
    st[x][y] = true;

    while(hh <= tt) 
    {
        pair<int, int> t = q[hh ++];//弹出队头
        //拓展队头我们使用循环，最后把中间那个点扣掉
        for(int i = t.first - 1; i <= t.first + 1; i ++)
        {
            for(int j = t.second - 1; j <= t.second + 1; j ++)
            {
                if(g[i][j] == '.') continue;
                //如果这个点不是水洼，那这个点不行
                if(i < 0 || i >= n || j < 0 || j >= m) continue;
                //如果这个点越界，那也不行
                if(st[i][j]) continue;
                //如果已经被搜到，不行（点：怎么这么残酷555😭😭😭）
                if(i == t.first && j == t.second) continue;
                //如果当前这个点是中间，继续踢走……
                //剩下的点可以做Flood_Fill
                //点：啊哈哈哈哈😁
                q[ ++ tt] = {i, j};
                //放进队列
                st[i][j] = true;
                //标记判重数组
            }
        }
    }
    //一切完毕
}
int bfs()
{
    int cnt = 0;
    //定义cnt
    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < m; j ++)
        {
            if(g[i][j] == 'W') 
            {
                //这个点必须是水洼才可以开始Flood_Fill
                if(!st[i][j])
                {
                    //这个点必须还没有搜过
                    //可以开始Flood_Fill
                    Flood_Fill(i, j);
                    //cnt ++
                    cnt ++;
                }
            }
        }
    }
    //最后返回cnt
    return cnt;
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i ++) scanf("%s", g[i]);
    //输入
    cout << bfs() << endl;
    //直接输出bfs
    return 0;
}