Реши задачу: Лабиринтом называется клетчатый квадрат 10*10, некоторые пары соседних узлов в котором соединены отрезком - "стеной" таким образом, что переходя из клетки в соседнюю по стороне клетку и не проходя через стены, можно посетить все клетки квадрата. Границу квадрата будем также считать обнесенной стеной. В некоторой клетке некоторого лабиринта стоит робот. Он понимает 4 команды - Л, П, В, Н, по которым соответственно идет влево, вправо, вверх и вниз, а если перед ним "стена", то стоит на месте. Как написать программу для робота, выполняя которую он обойдет все клетки независимо от лабиринта и от своего начального положения?



user
Решение
Рассмотрим все начальные состояния. Каждое состояние определяется лабиринтом и начальным положением робота в этом лабиринте. Тем самым, состояний всего конечное число. Занумеруем состояния числами 1,2,...,N. Нетрудно написать программу П1 обхода лабиринта исходя из начального состояния с номером 1. Далее, посмотрим, как двигался робот под действием программы П1 исходя из начального состояния номер 2. Припишем к программе П1 в конце несколько команд так, чтобы робот закончил обход лабиринта из начального состояния номер 2. Получим программу П2, выполняя которую, робот обходит лабиринт как из начального состояния номер 1, так и из начального состояния номер 2. Далее действуем таким же образом - приписываем к уже написанной программе Пk (выполняя которую робот обходит лабиринт из первых k начальных состояний), несколько команд так, чтобы робот обходил лабиринт и из (k+1)-го начального состояния. Полученная в конце программа ПN, как нетрудно видеть, будет искомой.
assistant