Minimum Moves to Reach Target in Grid - Solution & Explanation

Problem Overview: You start from a source cell in a grid and can transform the coordinates using specific additive moves. The goal is to reach a target cell using the minimum number of moves. Direct simulation grows extremely fast, so the challenge is recognizing the mathematical structure behind the transitions.

Approach 1: Forward BFS Simulation (O(Tx * Ty) time, O(Tx * Ty) space)

The most straightforward idea is to treat each coordinate pair as a node in a graph and run a BFS from the starting position. From a cell (x, y), generate the next valid states according to the allowed move rules and push them into a queue. BFS guarantees the first time you reach the target cell it is with the minimum number of moves. The downside is state explosion: coordinates grow quickly and the grid of reachable states can become enormous. This approach is mainly useful for reasoning about the problem or validating small cases.

Approach 2: Bidirectional BFS (O(min(Tx, Ty)^2) time, O(min(Tx, Ty)^2) space)

A common optimization for shortest‑path problems is running BFS from both the start and the target simultaneously. Each side expands one layer at a time until the search frontiers intersect. This significantly reduces the explored state space compared to plain BFS. However, the coordinate growth still makes the search impractical when the target values are large. The approach helps conceptually but still fails for typical competitive programming constraints.

Approach 3: Reverse Mathematical Reduction (O(log(max(Tx, Ty))) time, O(1) space)

The key insight is that the forward moves resemble additive growth such as (x + y, y) or (x, x + y). Instead of building up from the start, work backward from the target. If a coordinate became (x + y, y), the previous state must have been (x, y). Reversing the process repeatedly reduces the larger coordinate by multiples of the smaller one, which is equivalent to the modulo step used in the Euclidean algorithm. Continue applying tx %= ty or ty %= tx depending on which coordinate is larger, counting how many reductions correspond to moves. This greedy reduction quickly shrinks the target coordinates until they match the starting state or prove the path impossible.

This reverse process mirrors the greatest common divisor computation, which is why the complexity becomes logarithmic. The technique relies on mathematical invariants preserved by the allowed moves, making it far more efficient than exploring the grid explicitly. Problems like this often appear under math and number theory, even though the original statement looks like a grid traversal.

Recommended for interviews: Interviewers expect the reverse mathematical reduction. Starting with a BFS explanation shows you understand the graph interpretation, but recognizing the additive structure and converting it into a Euclidean-style reduction demonstrates strong problem‑solving skills. If the discussion involves state exploration or shortest paths, referencing BFS as the naive baseline before presenting the math optimization shows clear progression in reasoning.