Паркет из треугольников

prb47 Прямоугольную комнату размерами M на N (сначала по горизонтали, а потом по вертикали) замостили треугольными плитками и их пронумеровали, как показано на рисунке.

За один шаг можно переместиться с одной паркетины на другую только через общую сторону. Найти наименьшее количество шагов, нужных для перемещения с паркетины A на паркетину B.

Технические условия

Входные данные

Во входном файле в первой строке через пробел заданы значения M, N (1 ≤ M, N ≤ 100), а во второй - A, B.

Выходные данные

Искомое количество шагов.

Информация о задаче

Лимит времени: 1 секунда
Лимит памяти: 64 MB
Баллы за пройденный тест: 6.66667
Сложность: 30% 85/122

Пример

Пример входных данных

5 4
25 38

Пример выходных данных

← Отрезки

Список задач