아름다운 공원 timer 1s memory 256MB

KOIBS 교육방송국 스타강사 택쌤이 너무 많은 인기에 지쳐버렸다.

이에 택쌤은 강사생활을 1년간 잠시 중단하기로 하였다.

1년의 휴식 기간 동안 여유로운 생활을 하기 위해 어떤 일을 할까 고민하던 택쌤은, 그냥 심심해서, 스타강사 생활 동안 모은 자금을 바탕으로 시골에 있는 작은 공원 하나를 구입하였다. 

이 공원은 2차원 평면으로 나타낼 수 있는데, 현재 그림 1과 같이 각 단위 면적마다 심어져 있는 꽃이 다르다.​

공원의 출입구는 평면에서 (1,1)과 (N,M) 두 군데에 있는데, 택쌤은 택쌤의 공원을 한쪽 출입구에서 시작해서, 나머지 한쪽 출입구를 향해 산책할 때, 최단경로로 산책하는 사람들이 볼 수 있는 꽃의 순서가 항상 일정하기를 원한다.

(이유는 모르겠지만, 택쌤은 그러한 공원을 아름답다고 생각한다.)

그림 2를 참고해 보자

그림 2에서 푸른색 경로로 산책을 한다면 볼 수 있는 꽃의 순서는 1, 3, 4, 3, 1, 1, 3, 2 이고,

붉은색 경로로 산책을 한다면 볼 수 있는 꽃의 순서는 1, 2, 2, 1, 4, 3, 3, 2이므로, 두 경로에서 볼수 있는 꽃의 순서가 서로 다르다.

이는 택쌤이 생각하는 아름다운 공원의 조건에 맞지 않는다.

푸른색 경로(1, 3, 4, 3, 1, 1, 3, 2)와 보라색 경로 (2, 3, 1, 1, 3, 4, 3, 1)은 서로 다른 경로임에 유의하라.

검은색 경로 같은 경우는 최단경로가 아니므로, 고려할 필요가 없다. 

택쌤은 1의 비용을 들여, 각 단위 면적에 심어져 있는 꽃을 원하는 꽃으로 바꿀 수가 있다.

현명한 택쌤은 당연히 최소 비용으로 공원을 아름답게 만들고 싶다.

그림 1과 같은 경우는 그림 3처럼 수정하는 것이 가장 적은 비용(10)이 들게 된다. (그림 3이 최소비용으로 수정하는 유일한 방법은 아니다.)

그림 3을 보면 최단 경로로 산책할 경우, 보게 되는 꽃 종류의 순서가 항상 1, 3, 2, 1, 1, 2, 3, 1로 일치함을 알 수 있다.

현재 공원의 상태가 주어질 때, 택쌤이 보기에 아름다운 공원을 만들기 위한 최소 비용을 구하는 프로그램을 작성하시오.