0568MediumBreadth-First SearchHeuristic SearchBidirectional SearchA* Search

Survey Drone L-Hops

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A survey drone parks on an unbounded grid of landing pads, at pad (0, 0). Rows and columns run forever in both directions, so pad coordinates may be negative.

One hop takes the drone from pad (a, b) to any pad that is two rows and one column away, or one row and two columns away: the eight pads (a +- 1, b +- 2) and (a +- 2, b +- 1). There are no obstacles, and the drone may hop to pads outside the rectangle between its parking pad and its target.

Given a target pad (x, y), return the fewest hops that land the drone exactly on it. The target is always reachable.

Examples

Example 1

Input: x = 2, y = 1
Output: 1

Pad (2, 1) is two rows and one column from the parking pad, so a single hop lands on it.

Example 2

Input: x = 3, y = 3
Output: 2

The route (0, 0) to (1, 2) to (3, 3) uses two legal hops and finishes on the target.

Example 3

Input: x = -1, y = -1
Output: 2

The route (0, 0) to (-2, 1) to (-1, -1) uses two legal hops and lands on the target.

Constraints

-300 <= x, y <= 300
|x| + |y| <= 300

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_knight_moves(x: int, y: int) -> int:

Java

public int minKnightMoves(int x, int y)

The intended approach

Time O(|x| * |y|), the area of the bounded search box.Space O(|x| * |y|) for the reached-pad set and the layer lists.

The eight hops are unchanged when either coordinate's sign is flipped, so the distance to `(x, y)` equals the distance to `(|x|, |y|)` and the search only has to aim into one quadrant. Explore outward one hop-layer at a time from the parking pad, holding the current layer in a list and marking pads as they are reached, and report the layer number on which the target first appears. The search box reaches three pads beyond the target and three pads behind the origin on each axis, which leaves room for the short detours a shortest route needs when the target sits close to an axis, while keeping the explored area proportional to the target's coordinates.

Pythonentry point: min_knight_moves

def min_knight_moves(x, y):
    # O(|x| * |y|) time and space: the hop set is unchanged by flipping either
    # axis, so aim at the first quadrant, then run a layer-by-layer search over a
    # box that extends three pads past the target and three pads behind the
    # origin, which is the room a shortest route ever needs.
    tx = abs(x)
    ty = abs(y)
    if tx == 0 and ty == 0:
        return 0
    hops = ((1, 2), (2, 1), (-1, 2), (-2, 1), (1, -2), (2, -1), (-1, -2), (-2, -1))
    low = -3
    high_x = tx + 3
    high_y = ty + 3
    seen = set()
    seen.add((0, 0))
    frontier = [(0, 0)]
    steps = 0
    while frontier:
        steps += 1
        nxt = []
        for cx, cy in frontier:
            for dx, dy in hops:
                nx = cx + dx
                ny = cy + dy
                if nx < low or ny < low or nx > high_x or ny > high_y:
                    continue
                if (nx, ny) in seen:
                    continue
                if nx == tx and ny == ty:
                    return steps
                seen.add((nx, ny))
                nxt.append((nx, ny))
        frontier = nxt
    return -1

The obvious version

Lay out a padded rectangle of pads, set the parking pad's cost to zero and every other pad's cost to infinity, then repeatedly relax every pad against all eight hops until a full pass changes nothing, and read off the target's cost.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_knight_moves(x, y):
    hops = ((1, 2), (2, 1), (-1, 2), (-2, 1), (1, -2), (2, -1), (-1, -2), (-2, -1))
    lox = min(0, x) - 5
    hix = max(0, x) + 5
    loy = min(0, y) - 5
    hiy = max(0, y) + 5
    INF = float("inf")
    dist = {}
    for a in range(lox, hix + 1):
        for b in range(loy, hiy + 1):
            dist[(a, b)] = INF
    dist[(0, 0)] = 0
    changed = True
    while changed:
        changed = False
        for cell in dist:
            base = dist[cell]
            if base == INF:
                continue
            for dx, dy in hops:
                nb = (cell[0] + dx, cell[1] + dy)
                if nb in dist and dist[nb] > base + 1:
                    dist[nb] = base + 1
                    changed = True
    return dist[(x, y)]

How this problem was checked

Reference solution executed against 18 test cases — 18 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in