/ Vijos / 题库 /

巧克力饼

巧克力饼

时间限制:1秒  内存限制:256M


【问题描述】

  小H 对巧克力有一种狂热的爱好,他喜欢各种各样形状的巧克力。这天他得到了一些由 \(N×N\) 块小块构成的的矩形图案的巧克力,例如:
说明
  其中的每个'.'字符表示空的区域,每个'#'字符表示一块 1×1 的正方形格子大小的巧克力块。由于各种原因,矩形巧克力分裂成若干个互不相连的巧克力饼(上图中有两个)。一个巧克力饼是连通的,那么其中每个巧克力块的正方形格子都可以从这个巧克力饼中其他所有的巧克力格子出发重复地前往东、南、西、北四个方向上相邻的巧克力格子所到达。

  小H 想要知道每个巧克力饼的面积和周长。巧克力饼的面积就是这个巧克力饼种包含的’#’的数量,而周长则则是饼的轮廓线长。在上图中,小的巧克力饼的面积为 2 ,周长为 6 ,大的巧克力饼的面积为 13 ,周长为 22 。

  要注意的是。注意一个巧克力饼可能在中间有“洞”(由巧克力方块包围着的空的区域)。如果这样,洞的边界同样计入巧克力饼的周长。巧克力饼也可能出现在被其他巧克力饼包围的区域内,在这种情况下它们计为不同的巧克力饼。例如,以下这种情况包括一个面积为 1 的巧克力饼,被包围在一个面积为 16 的巧克力饼内:
说明
  同时求得巧克力饼的面积和周长十分重要,因为小H 最终想要最小化周长与面积的比值,他称这是他的巧克力方块的“巧周率”。当这个比率较小的时候,巧克力方块化得比较慢,因为此时巧克力方块单位质量的表面积较小。

【输入格式】

  输入的第一行包含 \(N\),以下 \(N\) 行描述了矩形巧克力图形的构成情况。其中至少出现一个'#'字符。

【输出格式】

  输出一行,包含两个空格分隔的整数,第一个数为最大的巧克力饼的面积,第二个数为它的周长。如果多个巧克力饼并列面积最大,输出其中周长最小的那一个。

【输入输出样例】

 Input

6
##....
....#.
.#..#.
.#####
...###
....##

 Output

13 22

【数据限制】

  \(100\%\) 的数据满足:\(1≤N≤1000\) 。

【来源】

  Mr.he

信息

ID
1329
难度
4
分类
搜索 | 图结构 点击显示
标签
递交数
7
已通过
1
通过率
14%
被复制
1
上传者