힘든 해병대 생활을 견디고 견뎌 해병대 훈련 교관(DI)이 된 02학번 광성이. 오늘은 새 기수 신병을 받는 날이다.
연병장에 가자 아니나 다를까, 가슴에 번호표를 단 훈련병들이 어리바리하게 흝어지어 있다. 초반부터 확실하게 군기를 잡고 싶었던 광성이. 메가폰을 잡고 운동장에 널브러져 있는 훈련병들을 향해 소리쳤다.
"자, 번호 상관없이 C열 종대로 줄 맞추어 섭니다. 실시!!!!"
쭈삣쭈삣 순서 상관없이 C열로 줄 맞추어 선 훈련병들. 해병대는 가입소 기간동안 자진하여 퇴소를 할 수 있다.
"자자, 본격적인 훈련을 시작하기 전에 집에 갈 사람들을 좌측으로 빠집니다. 실시!!"
중간중간 좌측으로 빠지는 훈련병들. 얼추 다 빠지고 보니 빈자리가 제법 보인다.
"동작 그만! 지금부터 빈자리를 채우겠습니다"
듬성듬성 있는 빈자리를 보며 광성이는 좌상단, 우상단, 좌하단, 우하단 네 꼭지점 중 어느 방향으로 밀착을 시켜야 느릿느릿한 훈련병들의 이동거리를 최소화 할 수 있을지 고민에 빠졌다.
광성이를 도와 훈련병들을 한 꼭지점을 기준으로 밀착시켰을 때 움직여야 하는 최소 이동거리를 출력하는 프로그램을 작성하시오.
훈련병들은 한 번에 상, 하, 좌, 우 중 한 방향으로만 밀착이 가능하며, 밀착 횟수는 제한이 없다.
첫 줄에는 테스트 케이스 개수 T (1 <= T <= 10)가 주어진다.
각 테스트 케이스마다 행의 수 R, 열의 수 C (1 <= R, C <= 1,000) 가 주어지고 이후 R줄에 걸쳐 C개의 번호가 주어진다.
번호는 0부터 R*C 범위 내 이고, 0은 빈자리를 의미한다. 0을 제외한 번호의 중복은 없다.
테스트 케이스 별로 한 줄로 빈자리를 채우기 위해 훈련병들이 움직여야 하는 최소 거리를 출력한다.
최소거리는 |원래 위치의 행 - 최종 위치의 행| + |원래 위치의 열 - 최종 위치의 열| 로 정의한다.
1
3 5
1 0 2 3 0
0 4 5 6 7
8 0 0 0 9
5
주어진 입력을 위로 밀착하여 빈자리를 채우면 다음과 같다.
1 4 2 3 7
8 0 5 6 9
0 0 0 0 0
이후 우로 밀착하여 빈자리를 채우면 최종적인 결과는 다음과 같다.
1 4 2 3 7
0 8 5 6 9
0 0 0 0 0
최종적으로 움직인 숫자는 4, 7, 8, 9 이고 각각 1, 1, 2, 1로 총 5만큼 이동하였다.
만약 좌로 밀착한 후 아래로 밀착했다고 가정해보자. 이 경우 최종 위치는 다음과 같다
1 2 0 0 0
4 5 3 0 0
8 9 6 7 0
최종적으로 움직인 숫자는 2, 3, 4, 5, 6, 7, 9 이고 각 1, 2, 1, 1, 2, 2, 3 이동하여 총 12 만큼 이동하여 앞서 이동한 것보다 더 크므로 정답이 될 수 없다.