파일 업로드

아이스크림 얼음 둘레 측정

profile
실행 시간 제한메모리 제한
2 초512 MB
📃 해결할 문제

재형은 아이스크림 사업을 시작하려고 합니다! 그는 아이스크림을 만드는 기계를 만들었지만 불행히도 이 기계는 다소 불규칙한 모양을 만들어냅니다. 그는 이 아이스크림 기계를 최적화하여 만들어내는 모양을 더 규칙적으로 만들기를 희망하고 있습니다. 기계가 출력하는 아이스크림의 구성은 N×NN \times N 그리드 (1N10001 \leq N \leq 1000)를 사용하여 다음과 같이 설명될 수 있습니다:

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

각 '.' 문자는 빈 공간을 나타내고, '#' 문자는 1×11 \times 1 정사각형 셀의 아이스크림을 나타냅니다. 

안타깝게도, 현재 기계가 제대로 작동하지 않고, 여러 개의 분리된 아이스크림 덩어리를 만들어냅니다. (위의 그림에는 두 덩어리가 있습니다). 

아이스크림 덩어리는 북쪽, 남쪽, 동쪽, 서쪽 방향으로 인접한 아이스크림 셀에 반복적으로 접근하여 덩어리의 다른 모든 아이스크림 셀에서 모든 아이스크림 셀에 도달할 수 있다면 연결된 것입니다. 재형은 가장 넓은 넓이의 아이스크림 덩어리의 면적과 둘레를 찾고 싶어합니다. 

덩어리의 면적은 덩어리의 일부인 '#' 문자의 수입니다. 만약 여러 덩어리가 가장 큰 면적으로 동점이라면, 그 중 가장 작은 둘레를 가진 것을 알고 싶습니다. 위의 그림에서는 작은 덩어리의 면적이 2이고 둘레가 6, 더 큰 덩어리의 면적이 13이고 둘레가 22입니다. 

덩어리 중에는 중앙에 '구멍'을 가진 것이 있을 수 있습니다(아이스크림으로 둘러싸인 빈 공간). 

이 경우, 구멍과의 경계선도 덩어리의 둘레에 포함됩니다. 또한 덩어리는 다른 덩어리 내에 중첩될 수 있고, 이 경우 별개의 덩어리로 취급됩니다. 예를 들어, 이 경우는 면적 16의 덩어리 안에 면적 1의 덩어리가 중첩된 경우입니다:

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

재형이 아이스크림 덩어리의 면적과 둘레 모두를 알아야 하는 이유는 둘레 대비 면적의 비율을 최소화하려고 하기 때문입니다. 이것을 그는 아이스크림의 얼음 둘레 측정치라고 부릅니다. 이 비율이 작을수록 아이스크림이 녹는 속도가 느려집니다. 왜냐하면 질량에 대한 표면적이 적기 때문입니다.

💻 입력
첫 번째 줄에는 NN이 주어지고, 다음 NN줄에는 기계의 출력을 설명합니다. 적어도 하나의 '#' 문자가 있을 것입니다.
🖨️ 출력

가장 큰 면적의 덩어리의 면적과 그 둘레를 나타내는 두 개의 공백으로 구분된 정수를 한 줄에 출력해 주세요. 

만약 면적이 가장 큰 여러 덩어리가 있으면, 둘레가 가장 작은 덩어리의 정보를 출력해 주세요.


💻 예제 입력 1
6
##....
....#.
.#..#.
.#####
...###
....##
🖨️ 예제 출력 1
13 22

출처: USACO 2019 January Contest, Silver Problem 2. Icy Perimeter