开始: 2025-07-10 17:50:00

暑假训练赛07

结束: 2025-07-10 20:40:00
当前  2025-07-16 10:43:05  类型: IOI  状态: 已经结束 

P3. 种田
描述

吴老师 在他的农田里种植了一种特殊的作物,然而播种机出现了故障,导致作物的分布形状不太规则。

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

其中 `.` 表示未种植作物的空地,`#` 表示一块 ( 1 \times 1 ) 的作物区域。  

定义与要求:  

1. **作物区域**:若一片作物中任意两块均可通过上、下、左、右(四方向)相邻的作物块连通,则称为一个连通的作物区域(即作物丛)。  

2. **面积**:作物区域中 `#` 的数量。  

3. **周长**:作物区域的边界长度,需注意:  

   - 外部边界(与农田外或空地相邻的边)计入周长;  

   - 内部"空洞"(被作物包围的空地)的边界也计入周长(即空洞的每一条与作物相邻的边都算周长)。  

**目标**:找到面积最大的作物区域,若有多个面积相同的,选择周长最小的那个,输出其面积和周长。  


输入

输入的第一行包含 N,以下 N 行描述了作物的生长情况。

其中至少出现一个 `#` 字符。

输出

输出一行,包含两个空格分隔的整数,第一个数为最大的作物区域的面积,第二个数为它的周长。

如果多个作物区域并列面积最大,输出其中周长最小的那一个的区域周长。

样例

输入

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

输出

13 22
提示

100%的数据,n\leq 1000

提交

题目参数
时间限制 1 秒
内存限制 128 MB
提交