LC: 1197. Minimum Knight Moves
1197. 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 <= 3000 <= |x| + |y| <= 300
The Essence:
Der Pfad, worauf sich der Springer auf dem Brett bewegen kann, enthält Muster. Zumindest muss sich der Springer immer in Richtung des Ziel bewegen. Daher kann sowohl eine von Anfang an ausdehnende Traversierung wie Sonarwellen als auch eine vom Ende rückwärts gehende Traversierung verwendet werden. Bei genauerer Betrachtung ergeben die Muster tatsächlich eine mathematische Formulierung, bei der einige Teile zwischen zwei Werten oszillieren und dann die nächsten Nachbarn dieser beiden in der nächsten Schicht oszillieren. Damit kann eine mathematische Berechnung mit konstanter Zeit erstellt werden.
Details:
Von den drei hier beschriebenen Ansätzen werden die ersten Zwei mit Breitensuche bzw. Tiefensuche implementiert.
Solutions:
Default Code:
Last updated