In an infinite chess board with coordinates from -infinity to +infinity, you have a knight at square [0, 0].
A knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.
Return the minimum number of steps needed to move the knight to the square [x, y]. It is guaranteed the answer exists.
Example 1:
Input: x = 2, y = 1
Output: 1
Explanation: [0, 0] → [2, 1]
Example 2:
Input: x = 5, y = 5
Output: 4
Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]
Constraints:
0 <= | x | + | y | <= 300 |
class Solution:
def minKnightMoves(self, x: int, y: int) -> int:
# combine similar cases
x = abs(x)
y = abs(y)
# queue from the start
q_s = deque([(0, 0)])
qed_s = set(q_s)
# queue from the end
q_e = deque([(x, y)])
qed_e = set(q_e)
# step counter
step = 0
while True:
# one layer from the start
for i in range(len(q_s)):
node = q_s.popleft()
# return condition: meet the other side
if node in qed_e:
return step
for nei in self.find_nei(node):
if nei not in qed_s:
q_s.append(nei)
qed_s.add(nei)
step += 1
# one layer from the end
for i in range(len(q_e)):
node = q_e.popleft()
if node in qed_s:
return step
for nei in self.find_nei(node):
if nei not in qed_e:
q_e.append(nei)
qed_e.add(nei)
step += 1
def find_nei(self, node):
alter = [
(1, 2),
(2, 1),
(-1, 2),
(2, -1),
(1, -2),
(-2, 1),
(-1, -2),
(-2, -1),
]
nei = [
tuple(node[i] + a[i] for i in range(2))
for a in alter
]
# remove obvious wrong answer
nei = [
n for n in nei
if n[0] > -2
and n[1] > -2
]
return nei
要点
while q:
和 while True:
没有区别,因为返回条件是在相遇处1,2
6,7,8
9,10,11
12,13
14
15,16
26,27
25
35
17
18
19
20
21,22,23,24
37
28,29,30,31,32,33,34
38,39,40,41,42,43,44,45,46,47
48,49,50,51
58
3,4,5
52,53,54,55,56,57
class Solution:
def minKnightMoves(self, x: int, y: int) -> int:
q = deque([(0, 0)])
qed = set(q)
step = 0 # special case, end is start
while True:
for i in range(len(q)):
# pop
node = q.popleft()
# process
if node == (x, y):
return step
# add nei
for nei in self.find_nei(node):
if nei not in qed:
q.append(nei)
qed.add(nei)
step += 1
def find_nei(self, node):
alter = [
(1, 2),
(2, 1),
(-1, 2),
(2, -1),
(1, -2),
(-2, 1),
(-1, -2),
(-2, -1),
]
return [
tuple(node[i] + a[i] for i in range(2))
for a in alter
]