8 Тезей, или Автоматическое построение лабиринтов
8
Тезей,
или Автоматическое построение лабиринтов
Тезей должен был найти выход из Критского лабиринта или погибнуть от руки Минотавра. Но что поразительно: найти вход в лабиринт — задача не менее трудная.
Здесь не представляется возможным описать все мыслимые лабиринты, да это и не требуется. Мы займемся простыми лабиринтами, построенными на прямоугольнике m?n, где m, n — положительные целые числа. Внутри и на границах прямоугольника поставлены стенки по ребрам покрывающей его единичной квадратной сетки. Чтобы построить из прямоугольника лабиринт, выбьем одну единичную стенку на одной из сторон прямоугольника (получится вход в лабиринт); выбьем одну единичную стенку на противоположной стороне (получится выход) и еще удалим какое-то число строго внутренних стенок. Говорят, что лабиринт имеет решение, если между входом и выходом внутри лабиринта есть путь в виде ломаной, не имеющей общих точек со стенками. Решение единственно, если любые два таких пути проходят через одни и те же внутренние ячейки сетки. На рис. 8.1 приведен пример лабиринта 6?6.

Рисунок 8.1. Пример лабиринта.
Тема. Напишите программу, которая по исходным данным m и n строит прямоугольный лабиринт m?n (проверьте, допустимы ли заданные тип). Предусмотрите, чтобы программа при каждом обращении к ней порождала разные лабиринты. Лабирипг должен иметь единственное решение, и, чтобы получившийся лабиринт был интересным, все ячейки должны быть соединены с основным путем, дающим решение. Если в вашем распоряжении имеется хорошее графическое устройство, используйте его для изображения лабиринтов, в противном случае придумайте систему обозначений для записи лабиринтов или выводите лабиринты на АЦПУ.
Указания исполнителю. Теоретически нельзя удовлетворить требованию, чтобы любые два лабиринта (даже при одинаковых m и n) были различны, поскольку существует лишь конечное число лабиринтов любого наперед заданного размера, а программу можно вызвать большее число раз. Однако число лабиринтов какого-нибудь размера очень велико, и поэтому вероятность повторения лабиринта можно сделать очень маленькой. Практически это достигается, если программа будет производить «случайный» выбор различных вариантов, опираясь на какое-либо доступное ей, но неуправляемое значение (обычно берут дату и время вызова программы). Варианты, между которыми выбирает программа, это, например, положение входа и выхода и положение хотя бы нескольких внутренних разрушаемых стенок. При отладке разумно будет отключить механизм случайного выбора, чтобы изменения результата работы вызывались только изменениями самой программы.
Один из возможных подходов к решению таков. Выбираем вход; затем, начав от него, добавляем по одной ячейке к главному пути-решению, пока он не достигнет выходной стороны. После этого удаляем некоторые внутренние стенки так, чтобы все клетки оказались соединенными с главным путем. Чтобы главный путь не получился прямым коридором, следует при его построении предусмотреть случайные повороты. Программа должна также следить за тем, чтобы при построении главного пути или при открытии боковых ячеек не нарушалась единственность решения. Наблюдательный читатель заметит, что определение единственности решения не годится в случае, когда путь заходит в боковой тупик и затем возвращается. Вы можете попробовать разработать в том же духе формально корректное определение.
Инструментовка. Программу можно написать почти на любом из процедурных языков. Используйте эту программу для сравнения языков с точки зрения управляющих структур, встроенных структур данных и эффективности выполнения.
Длительность исполнения. Одному исполнителю на 3 недели.
Более 800 000 книг и аудиокниг! 📚
Получи 2 месяца Литрес Подписки в подарок и наслаждайся неограниченным чтением
ПОЛУЧИТЬ ПОДАРОКЧитайте также
Автоматическое выравнивание
Автоматическое выравнивание Элемент <xsl:output> поддерживает атрибут indent который устанавливается в «yes» или «no», и указывает процессору XSLT, нужно ли выравнивать результирующий документ. Как правило, выравнивание результирующего документа не имеет большого значения,
Автоматическое создание юнитов
Автоматическое создание юнитов Зачастую бывает проблематично или неудобно вручную создавать весь список юнитов для большой сети. Для решения этой проблемы в netams–3.1(2000.204) была введена функциональность auto–units, или возможность автоматического создания юнитов при
Автоматическое обновление
Автоматическое обновление Следующее важное звено в обеспечении безопасности Windows – автоматическое обновление. Ценность своевременной установки обновлений заключается в том, чтобы избежать атаки злоумышленников через уязвимости в операционной системе. Поскольку Windows
4.3.5. Автоматическое определение принтера
4.3.5. Автоматическое определение принтера Вы настроили принтер, но при перезагрузке он не виден ни в окне конфигуратора, ни в других программах. Всe нормально.Скорее всего, принтер выключен или отключен от компьютера. Windows-пользователи начинают волноваться, потому что в Wining
Автоматическое обновление
Автоматическое обновление Служба предназначена для автоматического скачивания из Интернета и установки обновлений операционной системы и стандартных компонентов Windows XP. При этом сведения об уже установленных обновлениях берутся из реестра. Для этого предназначены
Автоматическое создание контента
Автоматическое создание контента Существует несколько способов автоматической и полуавтоматической генерации контента, причем каждый из них, в свою очередь, также допускает массу подходов и решений. Выбор того или иного способа зависит от типа контента, который должен
Автоматическое обновление
Автоматическое обновление Любой программный продукт постоянно дорабатывается и совершенствуется (если, конечно, он не снят с обслуживания и поддержки ввиду появления новых версий или по иным причинам). Это касается и операционной системы Windows 7: разработчики постоянно
Автоматическое обновление
Автоматическое обновление Купив последнюю версию Windows, вы покупаете не совсем последнюю версию. Пройдет совсем немного времени, и программисты компании Microsoft (или просто доброхоты-любители) обнаружат, что в системе есть уязвимость, через которую можно проникнуть на
Автоматическое дополнение слов
Автоматическое дополнение слов Средство Complete Word (Автоматически дополнить слово) редактора Visual Basic позволяет автоматически ввести практически любой VBA-термин. Активизируется это средство нажатием Ctrl +пробел. В результате на экране возникает список, наподобие
1.1.2. Автоматическое форматирование
1.1.2. Автоматическое форматирование Программисты, привыкшие работать в интегрированной среде разработки, оценят имеющиеся в Emacs средства автоматического форматирования кода. При открытии исходного файла, написанного на C/C++, редактор самостоятельно определяет наличие в
Автоматическое заполнение форм
Автоматическое заполнение форм Привычным атрибутом многих сайтов стала процедура регистрации. Подписка на рассылки новостей, получение нового электронного адреса, покупка программ через Интернет все эти услуги требуют регистрации и заполнения различного вида форм с
Автоматическое управление памятью
Автоматическое управление памятью Ни один из рассмотренных подходов не является полностью удовлетворительным. Общее решение проблемы управления памятью предполагает серьезную работу на уровне реализации
4.4.8. Автоматическое заполнение форм
4.4.8. Автоматическое заполнение форм Браузер Safari может автоматически заполнять поля электронных форм, заимствуя информацию из вашей личной карточки адресной книги. Более того, вы можете дать указание Safari запоминать все пароли и логины, используемые вами для доступа к
Автоматическое обновление
Автоматическое обновление Современные операционные системы – сложные программные продукты, и хакерам удается найти их слабые места, позволяющие получить контроль над компьютером. Когда об этом становится известно программистам из Microsoft, выпускается обновление
Автоматическое обновление ключей
Автоматическое обновление ключей Сертификат имеет ограниченный срок действия, который устанавливается в зависимости от возможностей современных криптографических алгоритмов и используемых длин ключей, а также с учетом практических соображений (например, объем