지프차 여행 timer 1s memory 256MB

현민이와 친구들은 오래된 지프차를 타고, 카우보이 복장으로, 서부음악을 들으며, 넓은 황야를 건너는 여행을 하려고 한다.

이 황야는 R×C칸으로 이루어진 2차원 평면으로 나타낼 수 있는데, 

각각의 칸은 특정한 값의 고도를 가지고 있다.

현민이는 이번 여행에서 다음 6가지 규칙을 지키려고 한다.

- 규칙 -

1. 현민이와 친구들은 즐거운 시간을 보내야 한다!

2. 현민이와 친구들은 지도의 가장 서쪽(왼쪽)의 아무 칸에서나 여행을 시작해서, 지도의 가장 동쪽(오른쪽)의 아무 칸에서나 여행을 끝낼 수 있다.

3. 현민이와 친구들은 현재 칸에서 다른 칸으로 움직일 때, 한 칸 동쪽(→), 북동쪽(↗), 또는 남동쪽(↘)으로만 이동할 수 있다. 

   단 황야 바깥으로 나가거나, 이동 불가능한 칸으로 움직이는 것은 할 수 없다. 

   (이동 불가능한 칸에 대해서는 아래에 추가적으로 설명되어 있다.)

4. 현민이와 친구들은 정확히 n번에 걸쳐 “협곡”을 통과해야 한다. 

   “협곡”이란, 인접한 북쪽 칸과 남쪽 칸의 고도가 현재 칸의 고도보다 높고, 인접한 서쪽 칸과 동쪽 칸의 고도가 현재 칸의 고도보다 낮은 칸을 말한다.

5. 현민이의 친구 중 한 명은 고소공포증이 있다.

    따라서 이번 여행 경로상에 있는 모든 칸들의 고도의 합이 최소가 되는 경로로 여행을 해야 한다.

6. 현민이와 친구들은 즐거운 시간을 보내야만 한다!

아래 그림 1의 황야 지도를 살펴보자.

그림 1

황야에는 물이 있거나, 도로가 포장되지 않는 등의 이유로 지프차로 들어갈 수 없는 칸도 있다.

그러한 칸들은 그림 1에서 검은색 칸으로 나타나 있다.

또한 "협곡"에 해당하는 칸은 회색 칸으로 나타나 있는 것을 확인할 수 있다.

황야의 바깥쪽 칸이나, 지프차로 들어갈 수 없는 칸과 인접한 칸은 당연히 협곡이 아니다.

현민이의 여행 규칙을 만족시키는 여행 경로에 놓인 칸들의 고도의 합을 출력하는 프로그램을 작성하라.