실행 시간 제한 | 메모리 제한 |
---|---|
1 초 | 128 MB |
공사장 안전관리자는 N (1 <= N <= 10,000)개의 라바콘을 가지고 있습니다.
만약 공사장을 100 x 100 그리드로 생각하고, 각 그리드를 1 x 1 정사각형 셀로 생각한다면, 각 라바콘은 그리드 셀 중 하나를 정확하게 차지합니다(두 개의 라바콘이 같은 셀을 차지하지는 않습니다).
안전관리자는 라바콘들이 모두 하나의 큰 연결된 지역을 형성하고 있음을 발견합니다. 즉, 어떤 라바콘에서 시작하여 북쪽, 남쪽, 동쪽, 또는 서쪽에 인접한 라바콘으로 이동하는 일련의 단계를 거쳐 다른 라바콘에 도달할 수 있습니다. 그러나, 이 연결된 라바콘 지역 안에는 '구멍'이 있을 수 있습니다. '구멍'은 라바콘에 완전히 둘러싸인 빈 지역을 말합니다.
'구멍'은 움직이지 않으며, 둘레에 기여하지 않는다는 점을 고려하여, 안전관리자가 라바콘으로 형성된 지역의 전체 둘레를 계산하는 데 도움을 주세요.
8 5 3 5 4 8 4 5 5 6 3 7 3 7 4 6 5
14
출처: USACO 2013 February Contest, Bronze Problem 3. Perimeter