sorohue   3년 전

문제

관호와 준성이가 여기저기 게임을 하려고 한다.

여기저기 게임은 특별한 게임판 위에서 진행되는 2인용 보드게임이다. 게임에 사용하는 게임판은  \( 3^D \times 3^D \) 크기의 하얀 정사각형 판을 이용해 만들 수 있다. 우선, 정사각형 판을 가로로 3등분, 세로로 3등분해 총 9개의 작은 정사각형 판을 만들고, 정가운데 판을 검게 칠한다. 남은 정사각형 판들 역시 각각 9개의 정사각형 판으로 쪼개고 정가운데 판을 검게 칠한다. 이 과정을 반복해 모든 정사각형 조각의 한 변의 길이가 1이 되도록 하면 게임판이 완성된다. 이때 왼쪽에서부터 x번째, 위에서부터 y번째 조각의 위치를 (x, y) 와 같이 나타낸다. 예를 들어, 게임판의 맨 왼쪽 위 조각의 위치는 (1, 1), 그 바로 오른쪽 조각의 위치는 (2, 1)이다. 아래는 N=2일 때 각 조각의 위치를 나타낸 그림이다.

preview

게임이 시작되면 두 플레이어는 서로 번갈아가며 공격과 수비를 맡는다. 공격 플레이어는 두 조각의 위치를 (x, y) 의 형식으로 제시한다. 이때 두 조각의 위치를 제시한 순서대로 '여기', '저기'라 부른다. 수비 플레이어는 '여기'와 '저기'의 위치를 듣고 '여기'에서 '저기'까지 이동하는 데 필요한 최소 이동 수를 계산해야 한다. 이동은 상하좌우로 인접한 조각으로만 할 수 있으며, 검게 칠해진 칸이나 게임판 바깥으로는 이동할 수 없다. 한 조각에서 상하좌우로 인접한 조각으로 움직이는 것을 한 번의 이동으로 센다. 예를 들어, N=2일 때 공격 플레이어가 (1, 1), (4, 8) 을 '여기'와 '저기'로 제시했다고 하자. 그러면 '여기'부터 '저기'까지 아래 그림과 같이 이동하면 이동 수가 최소가 되고, 이때 최소 이동 수는 10이다.

preview

만약 수비 플레이어가 정해진 시간 안에 최소 이동 수를 정확하게 계산했다면 수비 플레이어가 득점하고, 최소 이동 수를 잘못 계산했거나 주어진 시간 안에 계산하지 못했다면 공격 플레이어가 득점한다.

준성이는 이 게임을 매우 잘하기 때문에, 관호는 준성이에게 지지 않기 위해 자동으로 최소 이동 수를 계산하는 프로그램을 이용하고자 한다. 관호를 돕기 위해, '여기'의 위치 \( (H_C, H_R) \) 과 '저기'의 위치 \( (T_C, T_R) \) 이 주어졌을 때 최소 이동 수를 알려주는 프로그램을 만들자!

입력

첫 번째 줄에 테스트의 개수 T가 주어진다.
이후 총 T개의 테스트 케이스가 빈 줄로 구분되어 주어진다.
각각의 테스트 케이스는 하나의 줄로 이루어져 있고, 다섯 개의 양의 정수 D, HC, TC, HR, TR 이 공백으로 구분되어 순서대로 주어진다.

출력

각 테스트 케이스마다, 한 줄에 하나씩 '여기'에서 '저기'까지 이동하는 데 필요한 최소 이동 수를 출력한다.

댓글을 작성하려면 로그인해야 합니다.