StaffMath
Minimum Moves to Reach Target in Grid
You are given four integers sx, sy, tx, and ty, representing two points (sx, sy) and (tx, ty) on an infinitely large 2D grid.
You start at (sx, sy).
At any point (x, y), define m = max(x, y). You can either:
- Move to
(x + m, y), or - Move to
(x, y + m).
Return the minimum number of moves required to reach (tx, ty). If it is impossible to reach the target, return -1.
Example 1
Input
sx = 1, sy = 2, tx = 5, ty = 4Output
2The optimal path is
(1, 2) -> (1, 4) -> (5, 4), so the minimum number of moves is 2.Example 2
Input
sx = 0, sy = 1, tx = 2, ty = 3Output
3The optimal path is
(0, 1) -> (1, 1) -> (2, 1) -> (2, 3), so the minimum number of moves is 3.Constraints
- 0 <= sx <= tx <= 10^9
- 0 <= sy <= ty <= 10^9