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