파일 업로드

안전 구역의 둘레

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

공사장 안전관리자는 N (1 <= N <= 10,000)개의 라바콘을 가지고 있습니다. 

만약 공사장을 100 x 100 그리드로 생각하고, 각 그리드를 1 x 1 정사각형 셀로 생각한다면, 각 라바콘은 그리드 셀 중 하나를 정확하게 차지합니다(두 개의 라바콘이 같은 셀을 차지하지는 않습니다).

안전관리자는 라바콘들이 모두 하나의 큰 연결된 지역을 형성하고 있음을 발견합니다. 즉, 어떤 라바콘에서 시작하여 북쪽, 남쪽, 동쪽, 또는 서쪽에 인접한 라바콘으로 이동하는 일련의 단계를 거쳐 다른 라바콘에 도달할 수 있습니다. 그러나, 이 연결된 라바콘 지역 안에는 '구멍'이 있을 수 있습니다. '구멍'은 라바콘에 완전히 둘러싸인 빈 지역을 말합니다.

'구멍'은 움직이지 않으며, 둘레에 기여하지 않는다는 점을 고려하여, 안전관리자가 라바콘으로 형성된 지역의 전체 둘레를 계산하는 데 도움을 주세요.

💻 입력
  • 첫 번째 줄: 라바콘의 수, N.
  • 두 번째 줄..1+N 번째 줄 : 각 라인에는 하나의 라바콘의 (x, y) 위치가 포함되어 있으며, 여기서 x와 y는 모두 1에서 100 사이의 정수입니다. 위치 (1,1)은 공사장의 좌하단 셀을 나타내며, 위치 (100,100)은 우상단 셀을 나타냅니다.
🖨️ 출력
  • 첫 번째 줄: 연결된 라바콘 영역의 둘레.

💻 예제 입력 1
8
5 3
5 4
8 4
5 5
6 3
7 3
7 4
6 5
🖨️ 예제 출력 1
14

출처: USACO 2013 February Contest, Bronze Problem 3. Perimeter