실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 512 MB |
재형은 아이스크림 사업을 시작하려고 합니다! 그는 아이스크림을 만드는 기계를 만들었지만 불행히도 이 기계는 다소 불규칙한 모양을 만들어냅니다. 그는 이 아이스크림 기계를 최적화하여 만들어내는 모양을 더 규칙적으로 만들기를 희망하고 있습니다. 기계가 출력하는 아이스크림의 구성은 그리드 ()를 사용하여 다음과 같이 설명될 수 있습니다:
##....
....#.
.#..#.
.#####
...###
....##
각 '.' 문자는 빈 공간을 나타내고, '#' 문자는 정사각형 셀의 아이스크림을 나타냅니다.
안타깝게도, 현재 기계가 제대로 작동하지 않고, 여러 개의 분리된 아이스크림 덩어리를 만들어냅니다. (위의 그림에는 두 덩어리가 있습니다).
아이스크림 덩어리는 북쪽, 남쪽, 동쪽, 서쪽 방향으로 인접한 아이스크림 셀에 반복적으로 접근하여 덩어리의 다른 모든 아이스크림 셀에서 모든 아이스크림 셀에 도달할 수 있다면 연결된 것입니다. 재형은 가장 넓은 넓이의 아이스크림 덩어리의 면적과 둘레를 찾고 싶어합니다.
덩어리의 면적은 덩어리의 일부인 '#' 문자의 수입니다. 만약 여러 덩어리가 가장 큰 면적으로 동점이라면, 그 중 가장 작은 둘레를 가진 것을 알고 싶습니다. 위의 그림에서는 작은 덩어리의 면적이 2이고 둘레가 6, 더 큰 덩어리의 면적이 13이고 둘레가 22입니다.
덩어리 중에는 중앙에 '구멍'을 가진 것이 있을 수 있습니다(아이스크림으로 둘러싸인 빈 공간).
이 경우, 구멍과의 경계선도 덩어리의 둘레에 포함됩니다. 또한 덩어리는 다른 덩어리 내에 중첩될 수 있고, 이 경우 별개의 덩어리로 취급됩니다. 예를 들어, 이 경우는 면적 16의 덩어리 안에 면적 1의 덩어리가 중첩된 경우입니다:
#####
#...#
#.#.#
#...#
#####
재형이 아이스크림 덩어리의 면적과 둘레 모두를 알아야 하는 이유는 둘레 대비 면적의 비율을 최소화하려고 하기 때문입니다. 이것을 그는 아이스크림의 얼음 둘레 측정치라고 부릅니다. 이 비율이 작을수록 아이스크림이 녹는 속도가 느려집니다. 왜냐하면 질량에 대한 표면적이 적기 때문입니다.
가장 큰 면적의 덩어리의 면적과 그 둘레를 나타내는 두 개의 공백으로 구분된 정수를 한 줄에 출력해 주세요.
만약 면적이 가장 큰 여러 덩어리가 있으면, 둘레가 가장 작은 덩어리의 정보를 출력해 주세요.
6 ##.... ....#. .#..#. .##### ...### ....##
13 22
출처: USACO 2019 January Contest, Silver Problem 2. Icy Perimeter