193. Minimum Steps for a Knight to Reach a Target Square

On an n x n chessboard (0-indexed rows and columns), given a knight's starting square and a target square, find the minimum number of knight moves needed to reach the target.

Input: The first line contains n, the board size. The second line contains the knight's starting row and column. The third line contains the target row and column. Output: Print a single integer - the minimum number of knight moves to reach the target.

1 <= n <= 1000

This is a specific instance of 'shortest path on an unweighted graph' where the graph's EDGES aren't given explicitly but are instead COMPUTED on the fly from each square's knight-move rules - recognizing implicit graphs like this (rather than only explicitly-given ones) broadens which problems you'll recognize as BFS-solvable.

Find the minimum number of knight moves needed to travel between two squares on a chessboard. Brute force: Try every possible sequence of knight moves via DFS/backtracking, searching for the shortest one reaching the target - this can revisit the same squares many times through different move sequences, far less efficient than BFS's guaranteed shortest-first exploration. Optimised: Since every knight move has the SAME 'cost' (one move), this is exactly an unweighted shortest-path problem - BFS is guaranteed to find the target at the earliest possible level, which directly corresponds to the minimum number of moves needed.

Recursively try every sequence of knight moves from the start square, tracking visited squares to avoid immediate cycles, and record the length of any path that reaches the target, keeping the minimum found. Because DFS explores one long path at a time rather than expanding possibilities uniformly by distance, it offers no guarantee of finding the shortest path quickly - it can wander down long, ultimately-irrelevant branches before ever revisiting a shorter route, and without a depth cap it can take exponentially many steps to converge on the true minimum. Time: O(8^d) in the worst case (d = path length explored) Space: O(d) recursion depth

Run two BFS frontiers simultaneously, one expanding outward from the start square and one from the target square, always expanding whichever frontier is currently smaller, until the two frontiers meet; the sum of the two partial distances at the meeting point is the shortest path. Meeting in the middle keeps each frontier's explored region roughly half as 'deep', which in practice visits far fewer squares than a single one-directional search sweeping the whole board, especially when the two squares are close together relative to the board size - while still worst-case bounded by the board's size. Time: O(n^2) worst case, typically much less Space: O(n^2)

Treat every square as a graph node connected to the (up to 8) squares a knight can reach from it, and run a standard breadth-first search from the start square using a queue and an n x n visited grid, expanding move by move. Because BFS explores all squares reachable in k moves before any reachable in k+1 moves, the first time the target is dequeued its distance is guaranteed to be the minimum number of moves, and every square is enqueued at most once. Time: O(n^2) Space: O(n^2)

1. Model this as a shortest-path problem on an UNWEIGHTED graph, where each square connects to up to 8 others via the knight's possible moves. 2. BFS from the starting square finds the minimum move count directly, since BFS naturally explores in order of increasing distance. 3. Stay within the board's bounds when generating a square's knight-move neighbors, discarding any that would go off the edge.

Time: O(n²) in the worst case - each of the n² squares is visited at most once during the BFS. Space: O(n²), for the visited-tracking grid and the BFS queue.

Test the start square equal to the target (answer 0), a target near a corner of the board where fewer knight moves are available, and n at the upper bound of 1000.

Be ready to state clearly why BFS (not DFS) is the correct choice here - BFS's level-by-level exploration guarantees the FIRST time the target is reached is via the SHORTEST possible path, a guarantee DFS doesn't provide.