Условие
Лабиринтом называется клетчатый квадрат
10*10, некоторые пары соседних узлов в
котором соединены отрезком - "стеной" таким образом, что
переходя из клетки в соседнюю по стороне клетку и не проходя через
стены, можно посетить все
клетки квадрата. Границу квадрата будем также считать обнесенной
стеной.
В некоторой клетке некоторого лабиринта стоит робот.
Он понимает 4 команды - Л, П, В, Н, по которым соответственно
идет влево, вправо, вверх и вниз, а если перед ним "стена", то стоит
на месте. Как написать программу для робота, выполняя которую он
обойдет все клетки независимо от лабиринта и от своего начального
положения?
Подсказка
Перенумеруем все начальные состояния (определяемые лабиринтом и начальным
положением робота). Для каждого состояния напишем программу,
являющуюся продолжением программы для предыдущего состояния.
Решение
Рассмотрим все начальные состояния.
Каждое состояние определяется лабиринтом и начальным
положением робота в этом лабиринте. Тем самым, состояний всего
конечное число. Занумеруем состояния числами 1,2,...,N.
Нетрудно написать программу П
1 обхода лабиринта исходя
из начального состояния с номером 1.
Далее, посмотрим, как двигался робот под действием программы
П
1 исходя из начального состояния номер 2. Припишем к
программе П
1 в конце несколько команд так, чтобы робот
закончил обход лабиринта из начального состояния номер 2.
Получим программу П
2, выполняя которую, робот обходит
лабиринт как из начального состояния номер 1, так и из начального
состояния номер 2. Далее действуем таким же образом - приписываем
к уже написанной программе П
k (выполняя которую робот
обходит лабиринт из первых k начальных состояний), несколько
команд так, чтобы робот обходил лабиринт и из (k+1)-го начального
состояния. Полученная в конце программа П
N, как
нетрудно видеть, будет искомой.
Источники и прецеденты использования
