Минимизируйте ходы, чтобы достичь целевой точки из исходной точки, двигаясь по горизонтали или диагонали в правильном направлении.

Дан источник (X1, Y1) как (0, 0) и цель (X2, Y2) на двумерной плоскости. За один шаг любой из (X1+1, Y1+1) или (X1+1, Y1) может быть посещен из (X1, Y1) . Задача состоит в том, чтобы рассчитать минимальное количество ходов, необходимых для достижения цели, используя заданные ходы. Если цель не может быть достигнута, выведите «-1» .

Примеры:

Input: X2 = 1, Y2 = 0
Output: 1
Explanation: Take 1 step from (X1, Y1) to (X1+1, Y1), i.e., (0,0) -> (1,0). So number of moves to reach target is 1.

Input: X2 = 47, Y2 = 11
Output:  47

Наивный подход: наивный подход к решению этой проблемы состоит в том, чтобы проверить все комбинации (X+1, Y) и (X+1, Y+1) ходов, необходимых для достижения цели, и вывести наименьшее из них.

Эффективный подход: исходя из заданных условий движения, можно отметить следующие моменты:

• Если Y2 > X2, то мы не можем попасть в цель, так как при каждом ходе X должно увеличиваться на 1.
• Если Y2 < X2, то мы можем либо пройти по диагонали Y2 раза, а затем (X2-Y2) раз по горизонтали, либо наоборот.
• Если Y2 = X2, то мы можем пройти либо X2 раз по диагонали, либо Y2 ходов по диагонали.

Задачу можно решить, используя приведенные выше наблюдения. Если Y2 > X2 , то цель никогда не может быть достигнута за заданные ходы, иначе всегда необходимо минимум X2 ходов .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность : O(1)
Вспомогательное пространство : O(1)