셔틀 로봇의 이동 횟수

문제

1
3
0 2
2 0

4

1
8
1 6
2 4

1

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

5
28
0

입력 조건

• 가장 먼저 창고의 수 T가 자연수로 주어진다. T는 1 이상 5 이하의 자연수다.

• 이어서 T개의 창고에 대한 정보가 차례대로 주어지며, 각 창고의 정보는 세 줄로 이루어진다. 첫 줄에는 격자의 한 변의 크기 l이 주어진다. l은 3 이상 300 이하의 자연수다. 다음 줄에는 로봇이 서 있는 칸의 행과 열이 공백으로 구분되어 주어진다. 다음 줄에는 짐을 내려야 하는 칸의 행과 열이 공백으로 구분되어 주어진다. 행과 열은 모두 0 이상 l-1 이하의 정수이며, 두 칸이 서로 같을 수도 있다.

출력 조건

• 각 창고마다 로봇이 짐을 내려야 하는 칸까지 가기 위한 최소 이동 횟수를 한 줄에 하나씩 차례대로 출력한다. 서 있는 칸과 짐을 내려야 하는 칸이 같다면 0을 출력한다. 어떻게 움직여도 도달할 수 없다면 그 줄에는 -1을 출력한다.

요구사항

• 한 번의 움직임은 한 축으로 두 칸, 다른 축으로 한 칸입니다
• 여덟 가지 자리 가운데 격자를 벗어나는 곳으로는 갈 수 없습니다
• 격자 안에 로봇을 막는 것은 없습니다
• 창고마다 최소 이동 횟수를 한 줄에 하나씩 차례대로 출력합니다
• 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
• 쓸 수 있는 말은 파이썬, 자바스크립트입니다
• 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
• 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
• 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
• 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
• 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
• 케이스 15개를 전부 통과해야 해결입니다.

예시

공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.

1
8
1 6
2 4

1

1
3
0 2
2 0

4

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

5
28
0