백준 - 나이트의 이동

출처: Baekjoon Online Judge, https://www.acmicpc.net/

from collections import deque

loop = int(input())

for _ in range(loop):
    n = int(input())
    start = list(map(int, input().split()))
    dest = list(map(int, input().split()))

    chess = [[0]*n for _ in range(n)]
    if start == dest:
        print(0)
        continue

    def bfs(x, y):
        chess
        dx = [-2, -1, 1, 2, 2, 1, -1, -2]
        dy = [1, 2, 2, 1, -1, -2, -2, -1]

        queue = deque([[x, y]])
        while(queue):
            c_loc = queue.popleft()
            cnt = 0
            for _x, _y in zip(dx, dy):
                cnt+=1
                nx = c_loc[0] + _x
                ny = c_loc[1] + _y
                if nx > n-1 or ny > n-1 or nx < 0 or ny < 0:
                    continue
                if chess[nx][ny] == 0:
                    chess[nx][ny] = chess[c_loc[0]][c_loc[1]] + 1
                    queue.append([nx, ny])
                if nx == dest[0] and ny == dest[1]:
                    return chess

        return chess

    chess = bfs(start[0], start[1])
    print(chess[dest[0]][dest[1]])