Задача 3.
На плоскости расположено N точек. Имеется робот, который двигается следующим образом. Стартуя с некоторой начальной точки и имея некоторое начальное направление, робот движется до первой встреченной на его пути точки, изменяя в ней свое текущее направление на 90 градусов, т.е. поворачивая налево или направо. После этого он продолжает движение аналогично. Если робот достиг начальной точки, либо не может достичь новой точки (которую он еще не посещал), то он останавливается.
Определить, может ли робот посетить все N точек, если:
Определены начальные точка и направление робота.
Определена начальная точка, а направление робота можно выбирать.
Начальную точку и направление робота можно выбирать.
Координаты точек - целые числа, угол измеряется в радианах относительно оси ОХ.
|
Решение задачи 3.
Рассмотрим только случай, когда роботы двигаются только параллельно координатным осям, в других случаях можно сделать преобразование координат.
Легко понять, что если рассмотреть точку, имеющую наибольшую координату Y, причем самую левую (т.е. наименьшую координату Х, если таких несколько), то для нее существует только 2 возможность быть пройденной роботом: робот должен прийти из ближайшей точки А снизу и пойти в ближайшую точку Б справа или наоборот. В любом случае эти 2 отрезка фиксированы для робота. Теперь те же рассуждения можно провести и для точек Б и точки, находящейся правее Б, а также для самых нижних, левых и правых точек. Окончательно получается, что возможный проход робота строго фиксирован. Если упорядочить точки по горизонталям (вертикалям), то первая точка горизонтали (вертикали) должна соединятся со второй, третья с четвертой и т.д. Понятно, что если получившаяся фигура связна (цикл), то решение существует для случаев 2. и 3., а для случая 1. нужно проверить, в нужном ли направлении стоит робот. Однако есть одна трудность в случае, когда существуют горизонталь и вертикаль, содержащие нечетное число точек, а обход существует. Это возможно только в случае, когда это стартовая точка обхода, причем она находится в 'нечетной' горизонтали и вертикали. Удалив ее, можно воспользоваться предыдущей процедурой, при этом фиксированные отрезки не должны пересекаться в удаленной точке.
|
