Icy Perimeter

题目描述

Farmer John 要进入冰淇淋行业！他建造了一台机器来生产一团团冰淇淋，但不幸的是形状有些不规则，他希望优化机器，使输出的形状更合理。 机器输出的冰淇淋形状可以用一个 $N \times N$ 的网格（$1 \leq N \leq 1000$）来描述，例如： ##.... ....#. .#..#. .##### ...### ....## 其中每个 '.' 表示空白区域，每个 '#' 表示一个 $1 \times 1$ 的冰淇淋方格。

不幸的是，这台机器目前工作得不太好，可能会产生多个互不连通的冰淇淋团块（上图中有两个）。如果对于一个团块内的任意两个冰淇淋方格，都可以通过反复向北、南、东、西四个方向移动到相邻的冰淇淋方格而互相到达，则称该团块是连通的。

Farmer John 想要找出面积最大的冰淇淋团块的面积和周长。团块的面积就是属于该团块的 '#' 字符个数。如果有多个团块并列为最大面积，他希望在这些团块中选择周长最小的那个。在上图中，较小的团块面积为 2、周长为 6；较大的团块面积为 13、周长为 22。

注意，一个团块中间可能有“洞”（被冰淇淋包围的空白区域）。若存在洞，则洞的边界也计入该团块的周长。团块也可能嵌套在另一个团块内部，此时它们被视为不同的团块。例如，下图中有一个面积为 1 的团块嵌套在一个面积为 16 的团块内部：

#...# #.#.# #...#

同时知道团块的面积和周长很重要，因为 Farmer John 最终希望最小化“周长/面积”的比值，他称之为冰周度量（icyperimetric measure）。当这个比值较小时，冰淇淋相对于质量的表面积更小，因此融化得更慢。

输入格式

第一行输入 $N$，接下来 $N$ 行描述机器的输出。保证至少出现一个 '#' 字符。

输出格式

请输出一行，包含两个用空格分隔的整数：第一个为最大团块的面积，第二个为其周长。若有多个团块并列为最大面积，则输出其中周长最小者的信息。

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

13 22

提示

题目致谢：Brian Dean

标签: USACO|2019|Silver

来源

USACO|2019|Silver