/ Vijos / 题库 /

卫星照片

卫星照片

时间限制: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

信息

ID
1910
难度
(无)
分类
搜索 | 图结构 点击显示
标签
递交数
0
已通过
0
通过率
?
被复制
7
上传者