Городская олимпиада по информатике 1995/1996 г.
Тур I, Задача 2. "Лягушка и комар". 50 баллов
Лесное болото разделено на 8*8 одинаковых клеток. На одной из клеток сидит
лягушка, а над какой-то другой клеткой летает комар. Лягушка хочет съесть комара,
а комар старается от нее улететь. Перемещаются лягушка и комар по очереди,
первый ход за лягушкой. За один прыжок лягушка перемещается на любую из клеток
по горизонтали или вертикали. Комар за один перелет перемещается на одну из 8
соседних клеток. Если лягушка в прыжке пролетает через клетку, над которой
находится комар или прыгает на клетку, над которой летает комар, то она съедает
комара. В последнем прыжке лягушка может перемещаться по диагонали на одну клетку.
Требуется составить оптимальный алгоритм перемещения лягушки для того, чтобы съесть комара.
Внимание: отсчет начинается с левого верхнего угла.
Решение