- Minimum Knight Moves
中等 https://leetcode-cn.com/problems/minimum-knight-moves/
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:
-300 <= x, y <= 300
0 <= |x| + |y| <= 300
相关企业
- 谷歌 Google|5
- Facebook|5
- 亚马逊 Amazon|3
- 微软 Microsoft|2
相关标签
- Breadth-First Search
隐藏提示1
- You can simulate the movements since the limits are low.
隐藏提示2
- Is there a search algorithm applicable to this problem?
隐藏提示3
- Since we want the minimum number of moves, we can use Breadth First Search.
class Solution:
def minKnightMoves(self, x: int, y: int) -> int:
if x == 0 and y == 0:
return 0
stepcount = 0
myqueue_route_record = deque([[0, 0]]) # class collections.deque([iterable])
visitedsquares = set()
visitedsquares.add((0, 0)) # == set([(0,0)])
while myqueue_route_record:
stepcount += 1
currlevelLength = len(myqueue_route_record)
for _ in range(currlevelLength):
currcell = myqueue_route_record.popleft()
if self._checkEightDirections(currcell[0], currcell[1], myqueue_route_record, visitedsquares, x, y):
return stepcount
def _checkEightDirections(self, curr_x, curr_y, myqueue_route_record, visitedsquares, target_x, target_y):
offsets = [[1, 2], [1, -2], [-1, 2], [-1, -2], [2, 1], [2, -1], [-2, 1], [-2, -1]]
for offset in offsets:
new_x = curr_x + offset[0]
new_y = curr_y + offset[1]
if new_x == target_x and new_y == target_y:
return True
elif (new_x, new_y) in visitedsquares:
continue
else:
myqueue_route_record.append([new_x, new_y])
visitedsquares.add((new_x, new_y))class Solution:
def minKnightMoves(self, x: int, y: int) -> int:
if x == 0 and y == 0:
return 0
stepcounter = 0
forwardqueue_route_record = collections.deque([[0,0]])
forward_visitedcells = set([(0,0)])
backwardqueue_route_record = collections.deque([[x,y]])
backward_visitedcells = set([(x,y)])
while forwardqueue_route_record and backwardqueue_route_record:
stepcounter += 1
curr_level_length = len(forwardqueue_route_record)
for _ in range(curr_level_length):
currcell = forwardqueue_route_record.popleft()
if self.if8DirectionsContainTarget(currcell, forwardqueue_route_record, forward_visitedcells, backward_visitedcells, x, y):
return stepcounter
stepcounter += 1
curr_level_length = len(backwardqueue_route_record)
for _ in range(curr_level_length):
currcell = backwardqueue_route_record.popleft()
if self.if8DirectionsContainTarget(currcell, backwardqueue_route_record, backward_visitedcells, forward_visitedcells, x, y):
return stepcounter
return stepcounter
def if8DirectionsContainTarget(self, currcell, myqueue_route_record, visitedcells, opposite_visitedcells, targetx, targety):
offsets = [[1,2], [1,-2], [-1,2], [-1,-2], [2,1], [2,-1], [-2,-1], [-2,1]]
currx = currcell[0]
curry = currcell[1]
for offset in offsets:
newx = currx + offset[0]
newy = curry + offset[1]
if (newx, newy) in opposite_visitedcells:# this diff than BFS version
return True
elif (newx, newy) in visitedcells:
continue
else:
myqueue_route_record.append([newx, newy])
visitedcells.add((newx, newy))
return False