#395. 数水坑

    ID: 395 传统题 1000ms 128MiB 尝试: 1 已通过: 1 难度: 2 上传者: 标签>搜索深度优先搜索连通块八方向搜索CF

数水坑

题目描述

由于近期的降雨,雨水汇集在闹闹田地的不同地方。田地可以用一个 N×MN\times M 的网格表示,其中 1≤N,M≤1001\le N,M\le100。

每个格子只有两种情况:

  • W:这个格子中有水。
  • .:这个格子是旱地,没有水。

一个含水格子与其周围八个方向(上、下、左、右以及四个对角线方向)的含水格子相连。一组相互连通的含水格子构成一个水坑。

给定田地的网格图,求其中共有多少个水坑。

输入格式

第一行包含两个以空格分隔的整数 NN 和 MM,分别表示网格的行数和列数。

接下来 NN 行,每行包含一个长度为 MM 的字符串,仅由 W 和 . 组成,字符之间没有空格。

输出格式

输出一行一个整数,表示水坑的数量。

数据范围

1≤N≤1001\le N\le100,1≤M≤1001\le M\le100。

样例

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

样例说明

样例中的水坑分别位于左上角、左下角以及最右侧,共有 33 个水坑。

注意:仅通过对角线相邻的含水格子也属于同一个水坑。