Лабиринтом называется клетчатый квадрат 10*10, некоторые пары соседних узлов в котором соединены отрезком - "стеной" таким образом, что переходя из клетки в соседнюю по стороне клетку и не проходя через стены, можно посетить все клетки квадрата. Границу квадрата будем также считать обнесенной стеной. В некоторой клетке некоторого лабиринта стоит робот. Он понимает 4 команды - Л, П, В, Н, по которым соответственно идет влево, вправо, вверх и вниз, а если перед ним "стена", то стоит на месте.
Считаем, что программы - строки символов из алфавита Л, П, В, Н.
Клетки будем обозначать числами от 1 до 100.
Конкатенацию программ p и q будем обозначать p + q; клетку, в которую попадет робот, находившийся в клетке s, после выполнения программы p будем обозначать ps (очевидно, (p + q)s = q(ps)).
Если для каждого лабиринта существует программа, выполнив которую робот обойдет все клетки лабиринта, независимо от того, в какой клетке он находился в начале, контактенация всех таких программ (для всех лабиринтов) будет, очевидно, искомой программой.
Зафиксируем лабиринт, и построим такую программу.
Т.к. лабиринт связен (этого требования нет в постановке, но, очевидно, без него задача не имеет решения), для каждой клетки s существует программа t(s), под действием которой робот, находящийся в клетке s, обойдет все клетки лабиринта.
Обозначим p(1) = t(1).
Если уже построена программа p(s), выполняя которую, робот, находишийся в одной из клеток 1, 2, ..., s, обходит все клетки лабиринта, построим
p(s+1) = p(s) + t(p(s)(s + 1))
Робот, находившийся в состояниях 1, 2, ..., s под ее действием обойдет все клетки лабиринта (т.к. эта программа в начале выполняет p(s)).
Если же робот находится изначально в клетке s + 1, то он в начале под действием p(s) перейдет в состояние p(s)(s+1), а затем под действием t(p(s)(s+1)) обойдет все клетки лабиринта.
Т.о. под действием p(s+1) робот, находившийся в состоянии 1, 2,..., s + 1 обойдет все клетки лабиринта.
Так мы посторим p(s) для любого s = 1, 2, ..., 100. Очевидно, p(100) - искомая программа.