JOI 2012 예선, 2018camp contest3 problemD- 조명 > 문제은행 : 정보올림피아드&알고리즘




3156 : 조명

제한시간
2000 ms   
메모리제한
512 MB   
해결횟수
26 회   
시도횟수
237 회   

문제

인성이네 집은 아래 그림과 같이 1미터의 정육각형이 붙어있는 상태이다. 크리스마스가 다가오기 때문에, 여자친구에게 잘 보이기 위해 인성이는 건물의 벽면을 조명으로 장식하려고 한다. 외부에 보이지 않는 부분에 조명을 장식하는 것은 낭비라고 생각했기 때문에, 밖에서 보이는 부분만 장식하려고 한다.

 


 

 

위의 그림은 상공에서 본 인성이네 집의 건물 배치이다. 정육각형 안의 숫자는 좌표를 나타낸다. 여기서 회색 정육각형은 건물의 위치이고, 흰색은 건물이 없는 곳이다. 위에서 붉은 색 선으로 표시된 부분이 밖에서 보이는 벽이고, 이 벽에 조명을 장식할 것이다. 벽의 총 길이는 64미터이다.

 

인성이네 집의 건물 위치 지도가 주어졌을 때, 조명을 장식할 벽면의 길이의 합을 구하는 프로그램을 작성하시오. 지도의 바깥도 인성이네 집 바깥으로 친다. 변이 인접한 건물은 반드시 이어져 있으며, 이들의 경계는 바깥에서 볼 수 없다. 


입력형식

첫째 줄에 두 개의 정수 W와 H가 주어진다. (1≤W, H≤100) 다음 H줄에는 인성이네 집의 건물 배치가 주어진다. i줄에는(1≤i≤H) W개의 정수가 공백으로 구되어져 있다. j번째(1≤j≤W) 정수의 좌표는 (j, i) 이며, 건물이 있을 때는 1이고, 없을 때는 0이다. 주어지는 입력에는 건물이 적어도 하나 있다. 지도는 다음과 같은 규칙에 의해 만들어진다. 지도의 가장 왼쪽 위에 있는 정육각형의 좌표는 (1,1)이다. (x,y)의 오른쪽에 있는 정육각형의 좌표는 (x+1,y)이다. y가 홀수일 때, (x,y)의 왼쪽 아래(남서쪽)에 있는 정육각형의 좌표는 (x,y+1)이다. y가 짝수일 때, (x,y)의 오른쪽 아래(남동쪽)에 있는 정육각형의 좌표는 (x,y+1)이다.

출력형식

조명을 장식하는 벽면의 길이의 합을 출력한다.

입력 예

8 4
0 1 0 1 0 1 1 1
0 1 1 0 0 1 0 0
1 0 1 0 1 1 1 1
0 1 1 0 1 0 1 0

출력 예

64

입력 예

8 5
0 1 1 1 0 1 1 1
0 1 0 0 1 1 0 0
1 0 0 1 1 1 1 1
0 1 0 1 1 0 1 0
0 1 1 0 1 1 0 0

출력 예

56


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP