Решение задачи 471

Условие:

На шахматной доске в левом верхнем углу стоит робот. Ему надо попасть в правый нижний квадрат. За один ход он может переходить на любую соседнюю клетку (только не по диагонали). На доске есть непроходимый квадрат. Когда он получает инструкцию, например, вправо, а там стоит этот квадрат, то он остаётся на месте и выполняет следующую инструкцию по алгоритму. Придумайте алгоритм (конечную последовательность шагов), наверняка доставляющий робота в правый нижний квадрат (инструкции, направляющие робота за пределы доски, игнорируются).

Решение:

Рассмотрим такую последовательность действий (шагов): →, ↓, … , →, ↓ (16 движений). Покажем, что такой алгоритм работает.

1) Если непроходимый квадрат находится НЕ на главной диагонали и НЕ на диагонали, которая чуть выше главной, то робот без препятствий за 14 шагов доберется до нужной клетки (см рисунок):

2) Если непроходимый квадрат находится на главной диагонали, то робот не сможет сделать один из ходов вниз. На одном из последних шагов робот не сможет сходить вправо из-за правой стенки. Таким образом, робот доберется до нужной клетки за 16 шагов:

3) Если же непроходимый квадрат находится прям над главной диагональю, то робот не сможет сделать один их ходов вправо. Больше он холостых ходов делать не будет и доберется за 15 шагов до финиша:

Ответ: →, ↓, … , →, ↓ (16 движений).

Комментарий: Есть и другие решения.