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

Даны две точки P ₁ (x ₁ , y ₁ ) и P ₂ (x ₂ , y ₂ ) матрицы, задача состоит в том, чтобы найти минимальную стоимость достижения P ₂ из P ₁ , когда:

• Горизонтальное или вертикальное движение в любом направлении стоит 1 единицу.
• Движение по диагонали в любом направлении стоит 0 единиц.

Примеры:

Input: P₁ = {7, 4}, P₂ = {4, 4}
Output: 1
Explanation: The movements are given below given below:

Movements are (7, 4) -> (6, 5) -> (5, 5) -> (4, 4). 
As there is only 1 vertical movement so cost will be 1.

Input: P₁  = {1, 2}, P₂ = {2, 2}
Output: 1

Подход: Движения должны быть такими, чтобы было минимальное горизонтальное или вертикальное движение. Об этом можно судить по следующему наблюдению:

If the horizontal distance is h = (y₂ – y₁) and the vertical distance between the points is v = (x₂ – x₁):
If  |h – v| is even, only diagonal movements are enough. 
Because horizontal or vertical positions can be maintained with two opposite diagonal movements as shown in the image below:
 

maintaining vertical position

And when horizontal and vertical distances become same, then can directly move to P₂ using diagonal movements.
But in case this value is odd then one vertical or horizontal movement is required to make it even.

Для этого выполните следующие шаги:

• Найдите расстояние по вертикали от P ₁ до P ₂ . Скажем, это верт .
• Найдите горизонтальное расстояние от P ₁ до P ₂ . Скажем, это хори .
• Всегда будет путь от источника к месту назначения по диагонали, если |hori – vert| даже.
• Но если |hori – vert| нечетно, то требуется 1 шаг либо по горизонтали, либо по вертикали, после чего будет достаточно только движения по диагонали.

Ниже приведена реализация описанного выше подхода.

Сложность времени: О(1)
Вспомогательное пространство: O(1), так как дополнительное пространство не занято.