卫星照片
时间限制:1秒 内存限制:256M
【题目描述】
农夫 John 正在研究他的农场的卫星照片。照片为一个 \(R\) 行 \(C\) 列的字符矩阵表示。如下图:
图上的一块相连通的 "#" 表示一群奶牛或一个房间, 两个子"#" 连通的意思是说左右或上下相连。而下面的两块则是分开的:
John现在根据卫星照片上的的这些"#"块的形状来判断哪些是牛群,哪些是房间。如果一个"#"块形状的边是水平或垂直的矩形,则是房间。其它的则认为都是牛群。在第一个图中,有 3 个房间 ( 2x1, 2x5, and 1x1)和 2 群牛。
请根据输入文件中的数据,统计出房间数和牛群数,并计算他们形状的周长,数据中牛群不会包围另一个牛群或房间。
【输入格式】
第一行,两个整数: \(R\) 和 \(C\)。
第 \(2..R+1\) 行: 第 \(i+1\) 行表示照片的第 \(i\) 行情况,由 \(C\) 个字符组成。
【输出格式】
第一行: 房间数 \(m\)。
第二行: 牛群数 \(s\)。
第三行:\(s+m\) 个整数,牛群或房间的周长,输出顺序按照在照片上的分布中,按最上面#的位置从上到下,从左到右的顺序,如果没有房间或牛群,则无输出。
【输入输出样例】
Input
5 8
#####..#
#####.##
......#.
.###...#
.###..##
Output
2
2
10 4 6 3
【数据限制】
对于 \(100\%\) 的数据,\(1≤R,C≤75\)。
【来源】
Mr.he