[백준 7562 파이썬] 나이트 이동

# 7562 나이트 이동
# BFS
# Pypy3 752ms
 
 
dx = [-2, -1, 1, 2, -2, -1, 1 ,2]
dy = [-1, -2, -2, -1,1, 2, 2, 1]
 
def bfs(start, end):
    queue = [start]
    board[start[0]][start[1]]=1
 
    while queue:
 
        pos = queue.pop(0)
        if end[0]==pos[0] and end[1]==pos[1]:
            return board[pos[0]][pos[1]]-1
 
        for i in range(8):
            nx = pos[0] +dx[i]
            ny = pos[1] +dy[i]
            if 0<=nx <L and 0<=ny<L:
                if board[nx][ny]==0:
                    queue.append((nx, ny))
                    board[nx][ny]= board[pos[0]][pos[1]]+1
 
 
 
 
 
T = int(input())
for i in range(T):
    L = int(input())
    x1, y1 = map(int, input().split())
    x2, y2 = map(int, input().split())
    board = [[0]*L for _ in range(L)]
    if x1==x2 and y1==y2:
        print(0)
    else:
        print(bfs((x1,y1), (x2,y2)))