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

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

7562번: 나이트의 이동

Problem

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

 

조건

• 입력의 첫째 입력에는 테스트 케이스의 개수가 주어진다.
• 두번째 입력에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 
• 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

from collections import deque

dx=(1,2,2,1,-1,-2,-2,-1)
dy=(2,1,-1,-2,-2,-1,1,2)

T=int(input())


def bfs(x,y,f_x,f_y):
    dq=deque()
    dq.append((x,y))
    board[x][y] =1
    while dq:
        x,y =dq.popleft()
        if x == f_x and y == f_y :
            return board[x][y]-1 
        for k in range(8):
            ny=y+dy[k]
            nx=x+dx[k]
            if 0<=nx<N and 0<=ny<N :
                if board[nx][ny] ==0:
                    dq.append((nx,ny))
                    board[nx][ny] = board[x][y] +1


for _ in range(T):
	N=int(input())
	board=[[0]*N for _ in range(N)]
	x1,y1 = map(int,input().split())
	x2,y2 =map(int,input().split())
	if x1==x2 and y1==y2:
		print(0)
		continue
	ans=bfs(x1,y1,x2,y2)
	print(ans)