건우는 공간 이동 능력 마술사, 즉 점퍼이다.

건우의 목적은 r*c의 직사각형 모양으로 생긴 정올 시티의 몇 군데를 돌아다니면서 맛있는 짜장면을 빠르게 배달해 주는 것이다.

짜장면 집은 정올 시티 밖에 있다.

건우는 처음 순간이동을 할 때는 마력을 쓰지 않는다. 그리고, 다음 순간이동부터는 다음과 같은 규칙에 따라 마력을 사용한다.

- 새로 옮겨가고자 하는 좌표를 (x1, y1)라고 할 때, 여태까지 순간이동 했던(방문했던)

모든 (x,y)좌표를 고려해서 max(|x-x1|, |y-y1|)의 최댓값 만큼 사용한다.

예를 들어, 다음과 같은 경우를 보자.

가로 3, 세로 4의 정올 시티에서 1이라고 써 있는 곳에 짜장면을 배달해 줘야 할 경우를 살펴보자.

1 0 0 0

1 0 0 0

0 0 1 0

(3,3)로 먼저 순간이동한 후, (1,1)로 갈 때는 2의 마력이 든다. 다시 (2,1) 로 갈 때에는 (1,1)과 (3,3)과의 max(|x-x1|,|y-y1|)값을 모두 고려해서 2의 마력이 들어 총 4의 마력이 든다. 그러나 (1,1) -> (2,1) -> (3,3) 순으로 이동하면 3의 마력만으로 배달 할 수 있다.

건우가 배달이 끝난 후 마력을 채우는 데는 많은 시간이 들기 때문에, 건우는 순간이동에 필요한 마력을 최소화 시키려고 한다. 건우의 짜장면 배달에 필요한 최소 마력을 구하는 프로그램을 작성하라.

#3197 upload 23 done 5 how_to_reg 4

점퍼 timer 1s memory 256MB

#3197

점퍼 1s 256MB