Задача №114149. Мультиплеер в змейке
Компания Konia, специализирующаяся на выпуске бюджетных мобильных устройств, в последнее время теряет свои позиции на рынке. Ради спасения компании совет директоров пошел на отчаянный шаг: было решено внести изменения в самую известную игру, которая доступна на всех устройствах от Konia — «Змейку».
Правила этой игры очень просты. На клетчатом поле, состоящем из N строк и M столбцов, находится змейка, изначально имеющая длину 1 (т. е. представляющая собой квадратик 1 × 1 ). На каждом ходу змейка перемещается на одну клетку в одном из четырёх направлений: вверх, вниз, влево или вправо. Если при этом змейка пересекает какую-либо границу экрана, то она появляется с противоположной стороны. Например, сделав шаг влево из первой клетки четвёртой строки (будем говорить, что такая клетка имеет координаты (4, 1) ) на поле размером 10 строк на 8 столбцов, змейка окажется в клетке с координатами (4, 8) . Иногда на поле появляется еда, которая может увеличить длину змейки, но это не имеет отношения к данной задаче.
По предложению совета директоров в Змейку было решено добавить режим парной игры. Изначально змейки двух игроков появляются в разных клетках и имеют длину 1, то есть состоят только из клеток, в которых они появились. Каждый ход состоит из того, что сначала перемещается змейка первого игрока, а затем змейка второго игрока. Правила перемещения аналогичны описанным выше для одиночной игры, но, в отличие от одиночного режима, змейки имеют возможность столкнуться друг с другом, после чего игра заканчивается. Маркетинговые исследования показали, что пользователи предпочитают как можно более длинные игры, поэтому перед разработчиками стоит задача исследовать, как зависит длительность игры от начальных координат змеек ( a 1 , b 1 ) и ( a 2 , b 2 ) . Так как в режиме парной игры пока реализована только возможность передвигаться, еда на поле не появляется, и фактически игра сводится к управлению двумя одноклеточными змейками.
Вам, как ведущему инженеру компании, поручено контролировать деятельность коллег. Для это необходимо написать программу, которая по заданным размерам поля N и M и координатам двух различных клеток ( a 1 , b 1 ) и ( a 2 , b 2 ) вычисляет, на каком по счёту ходу впервые может возникнуть ситуация, что змейки столкнутся, то есть одна змейка совершит ход в клетку, в которой находится другая.
В первой строке ввода содержатся целые числа N и M ( 1 ≤ N , M ≤ 1 000 000 ), задающие соответственно количество строк и количество столбцов на игровом поле. Обратите внимание, что строки нумеруются от 1 до N снизу вверх, а столбцы — от 1 до M слева направо.
Во второй строке записаны два целых числа a 1 и b 1 ( 1 ≤ a 1 ≤ N , 1 ≤ b 1 ≤ M ) — изначальные координаты змейки первого игрока: сначала номер строки, затем номер столбца.
В третьей строке аналогично задаются a 2 и b 2 — изначальные координаты змейки второго игрока.
Гарантируется, что в начале игры змейки игроков находятся в разных клетках.
Выведите номер первого хода, на котором змейки могут столкнуться.
В первом тесте существует единственная клетка в которой змейки могут встретиться через один ход — клетка с координатами (5, 6) .
Тесты к этой задаче состоят из четырёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
5 8 5 5 5 7
1
10 10 1 1 10 10
1
10 4 3 1 10 3
3