Решение. Робот на шахматной доске (#71)
Идея в том, чтобы потерять на препятствии не более фиксированного числа ходов. Например, пусть робот меняет направление движения на каждом шаге. Рассмотрим следующий алгоритм
→, ↓, … , →, ↓ (16 движений)
Покажем, что данный алгоритм решает задачу. Рассмотрим две диагонали
— большую (соединяет левый верхний и правый нижний углы)
— маленькую (диагональ над большой диагональю)
1. Допустим, препятствие находится вне большой или маленькой диагонали. Тогда робот беспрепятственно достигает цели за 14 движений (7 пар →, ↓)
2. Пусть маленькая диагональ содержит препятствие. В данном случае после столкновения с ним, робот переходит на другую маленькую диагональ под большой диагональю и достигает цели за 15 движений.
3. Аналогично случаю 2 робот достигает цели, но уже за 16 движений.
