-
Notifications
You must be signed in to change notification settings - Fork 0
/
7562.py
39 lines (28 loc) · 851 Bytes
/
7562.py
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
32
33
34
35
36
37
38
39
from collections import deque
t = int(input())
dx = [-2, -1, 2, 1, -2, -1, 2, 1]
dy = [-1, -2, -1, -2, 1, 2, 1, 2]
results = []
for _ in range(t):
n = int(input())
start_x, start_y = map(int, input().split())
end_x, end_y = map(int, input().split())
board = [[0] * n for _ in range(n)]
board[start_x][start_y] = 1
q = deque()
q.append([start_x, start_y])
while q:
x, y = q.popleft()
if x == end_x and y == end_y:
results.append(board[x][y]-1)
break
for i in range(8):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= n or ny >= n:
continue
if board[nx][ny] == 0:
board[nx][ny] = board[x][y] + 1
q.append([nx, ny])
for result in results:
print(result)