문제
접근
BFS 문제이다.
단지 기존에는 2차원 공간에서 상하좌우로 움직였다면, 여기서는 조금 변형해서 8 곳으로 이동할 수 있다는 것만 다르다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from collections import deque
def bfs(sx, sy, ex, ey):
dx = [-2,-2,-1,-1,1,1,2,2]
dy = [1,-1,2,-2,2,-2,1,-1]
q = deque()
q.append((sx,sy))
while q:
nowx, nowy = q.popleft()
if nowx == endx and nowy == endy:
return board[nowy][nowx]
for x, y in zip(dx,dy):
nx = x + nowx
ny = y + nowy
if nx < 0 or nx >= s or ny < 0 or ny >= s:
continue
if board[ny][nx] == 0:
board[ny][nx] = board[nowy][nowx] + 1
q.append((nx,ny))
t = int(input())
for _ in range(t):
s = int(input())
board = [[0] * s for _ in range(s)]
startx, starty = map(int, input().split(' '))
endx, endy = map(int, input().split(' '))
ans = bfs(startx, starty, endx, endy)
print(ans)