[BOJ] 7562번 나이트의 이동 python

https://www.acmicpc.net/problem/7562

문제
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

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

output
5
28
0

import sys

def bfs(idx):
    q = [src[idx]]
    tmp = []
    cnt = 0

    if src[idx] != dest[idx]:
        while len(q) != 0:
            for pos in q:
                x = pos[0]
                y = pos[1]

                for i in range(8):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if -1 < nx < size[idx][0] and -1 < ny < size[idx][0] and not visited[nx][ny]:
                        if nx == dest[idx][0] and ny == dest[idx][1]:
                            return cnt + 1

                        visited[nx][ny] = True
                        tmp.append([nx, ny])

            q = tmp
            tmp = []
            cnt += 1

    return cnt


dx = [-2, -2, -1, -1, 1, 1, 2, 2]
dy = [-1, 1, -2, 2, -2, 2, -1, 1]

n = int(input())
input = sys.stdin.readline
size = []
src = []
dest = []
visited = [[False] * 300 for _ in range(300)]

for _ in range(n):
    size.append(list(map(int, input().split())))
    src.append(list(map(int, input().split())))
    dest.append(list(map(int, input().split())))

for idx in range(n):
    visited = [[0] * 300 for _ in range(300)]
    visited[src[idx][0]][src[idx][1]] = True
    print(bfs(idx))