Algorithm/BFS, DFS
[백준] 7562번 나이트의 이동
등촌동 꼬북이
2020. 9. 23. 23:57
쉬운문제..
그냥 한칸씩 이동에서 범위만 조금 넓어진 문제
from collections import deque
kDirection = [[-1, -2], [-2, -1], [-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2]]
def BFS(startX, startY, endX, endY, visited):
que = deque()
que.append([startX, startY, 0])
visited[startX][startY] = 1
while que:
cx, cy, cc = que.popleft()
if cx == endX and cy == endY:
print(cc)
break
for i in range(len(kDirection)):
nx = cx + kDirection[i][0]
ny = cy + kDirection[i][1]
if -1 < nx < L and -1 < ny < L and visited[nx][ny] == 0:
visited[nx][ny] = 1
que.append([nx, ny, cc + 1])
N = int(input())
for _ in range(N):
L = int(input())
visited = [[0] * L for _ in range(L)]
x, y = map(int, input().split())
targetX, targetY = map(int, input().split())
BFS(x, y, targetX, targetY, visited)