Ы общем, имеется некий виртуальный робот, запертый в прямоугольной виртуальной комнате. Его задача найти и обезвредить бомбу. Для обезвреживания роботу необходимо подобрать к бомбе код. Подсказки для кода хранятся в маяках, беспорядочно разбросанных по комнате. Длина кода неизвестна. За один ход робот может двигаться на одну локацию. У робота есть датчики чувствительности бомбы, стенки и маяка. Датчики работают если робот в той же локации что и бомба или маячок. Датчик стенки показывает, может ли робот двигаться в этом направлении.
подскажите плз, наиболее оптимальный алгоритм решения данной задачи (выполнить миссию за меньшее число ходов). Или хотя бы в каком направлении посмотреть.
(3) ну да, координаты бомбы, если встретишь, можешь сохранить, чтоб не искать потом. Но если количество маяков не задано, а обойти надо все, то только полный обход
По спирали от начальной локации, если не задан размер комнаты.
В случае обнаружения бомбы, возвращаться к ней по кратчайшей ломаной для проверки кода, после того как спираль достигнет стенок во всех напралениях.
Сложность алгоритма.
n*n+m*m
n m размеры
Требовать и эффективности, и гибкости от одной и той же программы — все равно, что искать очаровательную и скромную жену... по-видимому, нам следует остановиться на чем-то одном из двух. Фредерик Брукс-младший