Farmer John 一直想要好农场地图,买了一张土地的卫星照片,有 $R$ 行($1 \le R \le 75$)、$C$ 列($1 \le C \le 75$)。部分照片如下:
.................. ..#####.......##.. ..#####......##... .................. #.......###.....#. #.....#####.......
解读照片时,他认为每个连通形状是谷仓或奶牛。“连通形状”是一或多个 '#' 的集合,彼此上下或左右相邻。以下是两个不同连通形状:
.... .#.. ..#. ....
FJ 认为填满的矩形、四边平行 $x$ 和 $y$ 轴的连通形状是谷仓。首图有三个谷仓($2\times1$、$2\times5$、$1\times1$)和两头牛(某些牛的大小会令你惊讶!)。统计卫星照片的谷仓与牛数。
牛不会完全围住另一头牛或谷仓。
输入格式
- 第1行:两个空格分隔整数 $R$、$C$。
- 第 $2$ 至 $R+1$ 行:第 $i+1$ 行表示照片第 $i$ 行,含 $C$ 字符,无空格。
输出格式
- 第1行:谷仓数。
- 第2行:牛数。
样例
输入格式 1
5 8 #####..# #####.## ......#. .###...# .###..##
输出格式 1
2 2
说明
输入说明
照片5行,每行8字符。
输出说明
照片有2谷仓(左侧形状)、2头牛(右侧)。
题目作者:Brian Dean, 2004