Question
문제링크
Silver 1
Logic
기본 구조 :bfs
1. 나이트의 이동가능한 위치를 dx, dy로 정의한다.
2. 시작위치부터 이동 가능한 위치를 queue에 추가하여 목표 위치에 도달할 때 까지 탐색한다.
Code
from collections import deque
from sys import stdin
dx = [-1, -2, -2, -1, 1, 2, 2, 1]
dy = [2, 1, -1, -2, -2, -1, 1, 2]
def bfs(ax,ay,bx,by):
q = deque()
q.append([ax,ay])
li[ax][ay] = 1
while(q):
a,b = q.popleft()
if a==bx and b ==by:
print(li[bx][by]-1)
return
for i in range(8):
x=a+dx[i]
y=b+dy[i]
if 0 <= x < L and 0 <= y < L and li[x][y] == 0:
q.append([x, y])
li[x][y] = li[a][b] + 1
for i in range(int(stdin.readline())):
L = int(stdin.readline())
li = [[0]*L for _ in range(L)]
ax,ay = map(int,stdin.readline().split())
bx,by = map(int,stdin.readline().split())
bfs(ax,ay,bx,by)