Алгоритм поиска путей в лабиринте. Как найти выход из лабиринта: "Уралстудент" побывал в Зеркальном лабиринте

Одним из самых простых правил для прохождения лабиринта является правило "одной руки": двигаясь по лабиринту, надо все время касаться правой или левой рукой его стены. Этот алгоритм, вероятно, был известен еще древним грекам. Придется пройти долгий путь, заходя во все тупики, но в итоге цель будет достигнута. Хотя у этого правила и есть один недостаток, но о нем мы поговорим позже.

Попробуем описать робота, действующего в соответствии с правилом "правой руки".

В начале своей работы робот должен найти стену, по которой он будет следовать. Для этого он может просто двигаться вперед, пока не упрется в преграду.

После того как робот наткнулся на препятствие, он начинает передвигаться в соответствии с правилом "правой руки".

Двигаясь вдоль стены, робот следит, есть ли проход справа. Если проход есть, робот должен идти по нему, чтобы не оторваться от стены справа.

Если прохода нет - впереди стена - робот поворачивает налево. Если прохода снова нет, он еще раз поворачивает налево, таким образом разворачиваясь на 180 градусов, и идет в обратном направлении.

Блок-схема алгоритма для робота, работающего по правилу "правой руки", представлена на рисунке.

Попробуем проверить работу данного алгоритма и напишем для него программу. Для этой цели обратимся к среде программирования . Эта среда является удобным средством для моделирования различных алгоритмов, связанных с управлением роботами. В ней есть исполнитель черепаха, который по своей сути является не чем иным, как самым настоящим роботом. Черепаха располагает очень удобным набором команд - вперед, направо, налево, назад. Кроме того, в центре черепахи есть датчик, принимающий значение от 0 до 100, в зависимости от тона поверхности, на которой она находится.

Диалект языка Лого, который мы будем использовать, очень прост и похож на Basic. Познакомиться с командами языка можно . А бесплатно скачать среду программирования GameLogo - . Размер дистрибутива невелик - всего 1 Mb.

В архиве с GameLogo есть фоны с лабиринтами, одним из которых мы и воспользуемся.

В самом начале программы дадим команду черепахе, чтобы она подняла перо (по умолчанию черепаха оставляет после себя след).

Размер поля - 800 на 600 точек. Исходное положение для черепахи находится в месте с координатами 115, 545 (белый квадрат).

Цвет дорожек лабиринта - светлый, на них датчик будет принимать значения больше 50. Цвет стен лабиринта - темный, значение датчика будет меньше 50. Выход из лабиринта представлен черным квадратом, значение датчика над которым будет равно 0.

Объявим переменную флаг, с помощью которой будем контролировать, достигнут ли выход из лабиринта.

Напишем программу и запустим ее с помощью большой красной кнопки с надписью "Выполнить".

Переменная флаг фон = maze1.gif поднять перо место 115, 545 " поиск первой стены повторять пока датчик > 50 { вперед 12 } " правило правой руки повторять пока флаг = 0 { направо 90 вперед 12 если датчик = 0 то флаг = 1 иначе если датчик

Если известно, что у лабиринта нет отдельно стоящих стенок, то есть нет замкнутых маршрутов, по которым можно возвращаться в исходную точку, то такой лабиринт называют односвязным и его всегда можно обойти полностью, применив правило "одной руки".

Если же лабиринт содержит отдельно стоящие стенки, то, применяя правило "одной руки", не всегда можно пройти все коридоры и тупики. Лабиринты с отдельно стоящими стенками и с замкнутыми маршрутами называются многосвязными. При этом многосвязные лабиринты можно разделить на две группы: без "петли" вокруг цели (замкнутый маршрут не проходит вокруг цели) и с замкнутой "петлей" вокруг цели (цель можно обойти по замкнутому маршруту).

В многосвязных лабиринтах второй группы правило "одной руки" не работает и, применяя его, достичь цели невозможно. Но и эти лабиринты можно пройти, полагаясь на точный алгоритм.

Решение задачи о таких лабиринтах принадлежит сравнительно позднему времени, и начало ему положено Леонардом Эйлером. Эйлер не без оснований полагал, что выход из любого лабиринта может быть найден, и притом сравнительно простым путем.

Универсальный алгоритм прохождения любых лабиринтов был описан только через столетие в книге французского математика Э. Люка "Recreations matematiques", изданной в 1882 году. Интересно, что Люка при описании алгоритма указал на первенство другого французского математика М. Тремо. Таким образом, алгоритм стал известен как алгоритм Люка-Тремо .

Тремо предлагает следующие правила: выйдя из любой точки лабиринта, надо сделать отметку на его стене (крест) и двигаться в произвольном направлении до тупика или перекрестка; в первом случае вернуться назад, поставить второй крест, свидетельствующий, что путь пройден дважды - туда и назад, и идти в направлении, не пройденном ни разу, или пройденном один раз; во втором - идти по произвольному направлению, отмечая каждый перекресток на входе и на выходе одним крестом; если на перекресте один крест уже имеется, то следует идти новым путем, если нет - то пройденным путем, отметив его вторым крестом.

Зная алгоритм Тремо, можно скорректировать поведение легендарного Тесея. Вдохновленный подарком любимой Ариадны, он уверенно идет по лабиринту. Вдруг перед ним возникает ход, по которому уже протянута нить... Что делать? Ни в коем случае не пересекать ее, а вернуться по уже известному пути, сдваивая нить, пока не найдется еще один непройденный ход.

Применив вариант алгоритма Тремо, отец теории информации Клод Шеннон (Claude Elwood Shannon) построил одного из первых самообучающихся роботов. Шеннон дал ему звучное имя "Тесей", но в истории "Тесей" стал больше известен как "мышь" Шеннона. "Мышь" сначала обследовала весь лабиринт, а затем (во второй раз) проходила весь путь значительно быстрее, избегая участков, пройденных дважды.

На первой Российской Олимпиаде Роботов проводились соревнования, целью которых было прохождение своеобразного лабиринта: за наиболее короткое время, двигаясь через "открытые двери" в стенках, робот должен был добраться от места старта до места финиша. Контролировать свое движение робот мог по черным линиям, нанесенным на пол лабиринта.

Лабиринтом в Path of Exile называется то подземелье, в котором присутствуют ловушки, разнообразные головоломки, а также и монстры. Как завершиться уровень, то можно обратно войти в лабиринт, при этом используя Статую Богини, находящуюся в Сандрии. В самом лабиринте вы отыщите не только ловушки, но многочисленные испытания Восхождения, при этом спрятана одна ловушка, про которую мало кто знает. Но ловушку просто так не отыскать, ибо она будет спрятана случайным образом в любой из представленных групп, где испытание такое считается уже смертельным, для этого мы подготовили прохождение данного лабиринта.

При повышении сложности на уровне, появляется новая структура комнат (прохождение лабиринта осложняется), где они остаются прежними лишь одни сутки. Но сами комнаты, по сути, между собой одинаковы, но не все могут совпадать по точности планировки. Абсолютно каждые сутки производиться изменение структур комнат. Конечно же, просто так это не пройти, где имеются специальные ключи, чтобы открывать двери, но они будут находиться за тяжелопроходимыми ловушками. Если же откроете ключом комнату, то появится целый зал, соединяющий несколько комнат.

После того как игрок окажется в этом лабиринте, то постоянно будет встречаться с Изарием. Каждое ваше действие повиляет в последующих сражениях. Где первое сражение будет продолжаться, пока планка здоровья вашего врага не достигнет 2/3, после 1/3, а дальше необходимо полностью одержать победу. Но в последнем сражении не забудьте, что будут присутствовать ловушки и действовать надо аккуратно.

Ровно 45 минут потребуется опытному игроку, который уже знает, что и к чему относится. Если вы будете находиться в лабиринте Правителя, то у вас не будет права на телепорт в город, тем самым придется пройти лабиринт заново. Соответственно, ограничений в этой игре нет, и можете испытывать все методы прохождения.

Изначально, когда будете проходить игру в первый раз, то доступен будет класс лишь Восхождения. С каждым разом вы будете на протяжении игры получать очки, которые можно будет потом обменять на умения. При этом вы сможете чаровать предметы, но выбрав лишь один.
Если же кто-то из игроков проходит лабиринт быстрей всех в какой-то из дней, то ему предоставляют специальный приз с уникальными самоцветами. Причем все рейтинги о прохождениях, вы можете посмотреть на официальном сайте. Чем выше сложность уровня, тем выше награда за него будет предоставляться.

Как открыть и попасть в лабиринт?

Для того чтобы оказаться в основном лабиринте, который нам нужен, требуется сначала отыскать шесть малых лабиринтов, где их нужно сначала отыскать и пройти.

• Этап 1: Тюремное подземелье (The Lower Prison);
• Этап 2: Обитель грехов, уровень 2 (Chamber of Sins Level 2);
• Этап 2: Склеп, уровень 1 (The Crypt Level 1);
• Этап 3: Крематорий (The Crematorium);
• Этап 3: Катакомбы (The Catacombs);
• Этап 3: Зеленый лабиринт (The Hedge Maze) – полноценного телепорта на эту карту изначально не было предусмотрено, но оказаться там все же можно, если вы попадете в нее через Имперские сады (The Imperial Gardens).

Тем самым, главный лабиринт будет находиться в 3-ем этапе, который будет располагаться в городе. Каждый из мини-лабиринтов нужно пройти по одному разу, тем самым откроете доступ к главному лабиринту, причем это будет совершено навсегда, для той сложности, на которой вы проходите.

Гайд — как пройти лабиринт правителя Path of Exile

Сражения с боссами

В основном лабиринте присутствует три сложных сражения с Изарием, который обладает многофункциональностью и сменой образа, то есть при каждом сражении, у него будут помощники, но постоянно разные.

• Первый этап. В этом этапе появляются статуи, которые начнут ему помогать. Но появляются они не сразу, где есть два варианта, как разобраться со статуями. Это временно обезвредить и разрушить их окончательно. После того как найдете единственное решение из них, то вам придется наносить последующие уроны уже по боссу. Если же не разберетесь со статуями, то у него появится дополнительная защита на финальных моментах, где станет не так легко одержать над ним победу.

• Второй этап. В этом этапе ему помогают небольшие боссы, которые не такие эффективные, как главный босс, но вполне могут нанести хороший урон. Их появление происходит постепенным, где нужно придерживаться прежней тактики. Убираем помощников, а потом расправляем с боссом.

• Третий этап. В этом этапе вам важно занять такую позицию, чтобы ловушки вас никак не достали и могли спокойно наносить урон по боссу. Но это только в тот момент, когда вы дошли до этого этапа без помощников, то есть разобрались с ними в предыдущих этапах.

А также стоит помнить, что в одной из версий присутствует Изарий, умеющий использовать телепорт против вас прямо на ловушки, что усложнит задачу по сражению с боссом.

Пройдя третий этап, вы оказываетесь на новой карте. В ней, имеете право зачаровать некоторые предметы, взять дополнительно подкласс, открывать сундуки, которые можно открыть при помощи ключей, найденные вами на протяжении прохождения лабиринтов.

Стоит учитывать то, что в лабиринтах иногда появляются такие зоны, которые называют «зверь». Если же отыскать эту зону и уничтожить ее, то будущий босс будет значительно слабым соперником. Это хоть и облегчит вам задачи, но особого адреналина в прохождении уже не будет, так что вам решать.

Ловушки в лабиринте правителя Path of Exile

Несомненно, в лабиринтах присутствуют ловушки, но не одного типа, а нескольких, которые являются не просто опасными, но и смертельно опасными штуками. Где могут отнимать не только состояние щита, но и здоровья. Про большинство ловушек можно узнать в Испытаниях Восхождениях, где показано немалое количество таких ловушек.

В некоторых квадратных областях находятся шипы, которые не сразу можно заметить, ибо они появляются через определенное количество времени. Причем некоторые такие ловушки появляются лишь, когда вы наступите на них. Урон примерно составляет четверть общего здоровья, то есть в нее включается не только здоровье, но и ваш щит. Наступив на ловушку, вы замедлит на пару секунд, и получаете хорошее кровотечение. Такой вид ловушек самый безобидный, ибо повторное его действие проходит не сразу, а спустя какое-то время. Причем урон наносится разово и не продолжает свое действие. Такие нанесенные уроны можно восстановить при помощи флаконов наполненные здоровьем.

Чтобы узнать, как действуют ловушки такого типа, то можете посмотреть на локации первого этапа, а если точней, то в Тюремном подземелье.

Пилы способны двигаться по заданной траектории, повторяя свои действия раз за разом. Где урон может быть постепенно наносимым, но это намного эффективней, чем обычные шипы. Где урон в этом случае не важен. Порой пилы можно временно выключить, если отыскать и выключить рычаг. Чтобы узнать, как они действуют, то отправляйтесь на карту второго этапа в Обители грехов 2.

Вращающиеся клинки обладают сложной системой передвижения и воздействия на игрока, который находятся на полу. Если же игрок вступит в контакт с этой ловушкой, то получит сокрушительный урон, от которого будет сложно вылечиться. Где траектория передвижения у них постоянно может изменяться. Но все можно временно отключить, если отыскать рычаги. Их можно увидеть в Склепе на втором этапе.

Плавильные ловушки представляют собой пустые квадраты, которые постепенно пополняются магмой и на это уходит определенное количество времени. Убийство магмой проходит за пять секунд, где мгновенно уменьшается здоровье, но можно избавиться, если выпьете флакон со здоровьем и покинете ту ловушку. По монстрам такой урон не проходит, ибо они сопротивляются огню. Такие ловушки находятся в Крематории, а это третий этап.

Стражи с клинками, они довольно большие ловушки, которые невозможно не заметить, от которых наносится значительный урон, наносимый урон может быть постепенным. Чем ближе находитесь к центру этой ловушки, то урон будет увеличиваться. При этом ловушка меняет свою траекторию, что усложняет прохождение лабиринта. Именно они находятся в Катакомбах на третьем этапе.

Летающие дротики, ловушка, которая стреляет исключительно небольшими снарядами, она может менять свое направление. Снаряды стреляют через заданный промежуток времени. Наносимый урон не столь велик, но пережить несколько выстрелов можно, при этом он вас будет замедлять. Такие ловушки будут находиться на стенах и столбах, некоторые из них активируются при помощи нажатия определенных плит. Для оценки стрельбы ловушек, можете посетить Зеленый лабиринт в третьем этапе.

Сторожи, те ловушки, которые оказывают на вас и окружающую среду вредоносный урон, действующий определенное время, а такие ловушки встречаются лишь на 75 уровне.

Дополнительные (секретные) ловушки в лабиринет

Конечно же, существует еще и другая масса ловушек, которые менее известны людям. Одной из таких ловушек являются вращающие лезвия, вращаются вертикальным образом в дверях.

Игроков постоянно сортирует система, и это зависит от количества затраченного времени на прохождения лабиринта. Чтобы получить единоличное лидерство в лабиринте, требуется одному пройти лабиринт. Причем лабиринт должен быть пройден до конца дня, пока не произошли никакие изменения. В результате всего получиться двенадцать лидеров по лабиринтам на разных уровнях сложностях.

• Чтобы играть в списке обычных игроков, требуется не переходить планку 40-го уровня.
• Чтобы играть в списке жестоких игроков, требуется не переходить планку 60-го уровня.
• Чтобы играть в списке безжалостных игроков, требуется получить 60-ый уровень и выше.

В полночь решается судьба всех игроков, которые решили принять участие, где начинается самое интересное, а если точней, то распределение призовых мест, наград и других интересных вещей. Причем все зависит от сложности уровня, затраченного времени и так далее. Причем награды присуждаются некоторым игрокам в течение дня, а это осуществляется примерно 4 раза.

Более того, здесь же можно прикоснуться к таинственному миру зазеркалья.

В самом сердце города, на улице Вайнера, 15 открылись лабиринты зеркал и страха.

Заходя сюда с оживленного "Екатеринбуржского Арбата", не чувствуешь никакого подвоха. Приветливая девушка-администратор предлагает испытать себя: сумеешь ли ты войти в лабиринт зеркал с одного входа и выйти через другой? Со стороны кажется, что все просто. Достаточно всего лишь внимательно смотреть по сторонам: с одной все равно будешь отражаться неверно. Но это невозможно: одно неправильное движение - и ты попадаешь в тупик.

	Люди у нас часто теряются, - рассказывает управляющая Екатерина Луч-Демченко. - Некоторые устают и начинают звать на помощь, тогда мы выводим их. Заметила, что люди, которые в жизни находят выход из самых тупиковых ситуаций, выбираются и из лабиринта. Один упорный мужчина блуждал целых полтора часа. Знал, что все равно выберется.
Пока мы разговариваем, зашли две женщины с маленькими девочками. Дети в восторге: они вызвались сами прокладывать путь своим мамам. На удивление, не прошло и 30 минут, как раздались радостные возгласы: "Ура, нашли!" . Это значит, что блуждающим удалось-таки обнаружить единственный проход на другую сторону. - Наш лабиринт даже длиннее, чем в Москве и Питере , - продолжает Екатерина. - Уборщицы теряются, пытаясь найти обратный выход. Теперь находим их по проводу от пылесосов. Кстати, у них теперь самые модные "селфи" - то и дело фотографируются на фоне зеркал. Поблуждав какое-то время, спрашиваем то, что нас интересует еще больше. Так ли страшен второй лабиринт, как рассказывают о нем те, кто уже побывал? - А вы посмотрите сами, - предлагает Екатерина. Вдруг из-за стены (именно там и находится "Лабиринт страха") раздаются душераздирающие вопли и громкие стуки
- Наверное, люди просто слишком эмоциональны , - усмехаюсь я, еще не представляя, что нас ждет. Итак, на всякий случай отправив фотографа Женю идти первым, ступаю вслед за ним. Все, как в настоящих фильмах ужаса: нарастающая тревожная музыка, чарующая темнота, тусклое мерцание света. Ты самонадеянно думаешь, что пугать тебя будут фигуры скелетов и страшных кукол, но уже после первого поворота понимаешь, как сильно ошибался.

Я визжу от ужаса и вцепляюсь в фотографа. Женя ступает уже мене уверенно, но все равно идет вперед. Пока на его обрушивается новая опасность, меня она настигает как идущую позади. И я вспоминаю, что по законам фильмов ужасов, никакое положение не гарантирует тебе безопасности.

Наше путешествие в мир страха продлилось минут 15, но они показались мне вечностью. Я выхожу и истерично смеюсь, тогда как внутри все сжимаетя от пережитого ужаса.

-Ну как? - улыбаетя Екатерина.

Никакие комнаты страха из "Луна-парков" не идут в сравнение с лабиринтом на Вайнера, 15. Ведь даже взрослые мужчины истошно кричат в его стенах. Поэтому, приводя сюда на свидание свою девушку, имейте ввиду, что неизвестно еще, кому придется защищать другого.

Сейчас в лабиринт приходят в среднем 200 человек за день. Цена билетов одинакова и для детей и взрослых: 200 рублей за лабиринт зеркал и 300 - за вход в лабиринт страха. Если посещаете оба, приготовьте 450 рублей. Детям от 6 до 12 лет вход в лабиринт страха возможен только в присутствии родителей.

Нововведение из российских столиц уже появляется в других крупных городах. В Екатеринбурге же в ближайшее время планируется еще несколько проектов. Так, в июне пойдут два флеш-моба. Один из них - собрание самых жутких персонажей фильмов ужасов.

Секретом остается появление в нашем городе нового заведения от создателей лабиринтов.

- Это будет не менее интересный проект для горожан, - утверждает Екатерина.

Кристина Ермак,
фото Евгения Брюховецкого

Мне нравится

Доброго времени суток, уважаемое сообщество.

Предыстория

В один прекрасный день, гуляя просторами интернета, был найден лабиринт. Интересно стало узнать его прохождение и погуляв еще по сети, я так и не нашел, рабочей программной реализации, решения лабиринта.

Вот собственно и он:

Рабочий день был скучный, настроение было отличное. Цель, средства и желание имеются. Вывод очевиден, будем проходить.

История

Для удобного решения, необходимо имеющееся изображение лабиринта, привести к типу двумерного массива. Каждый элемент которого может принять одно из 3-ех значений:

Const WALL=-1; BLANK=-2; DEADBLOCK=-3;

Наперед, хочу показать функции для сканирования изображения лабиринта с последующей записью данных в массив, и функцию генерации нового изображения, на основании данных из массива:

Сканирование изображения:

Var N:integer=600; LABIRINT:array of integer; ... var bit:TBitmap; i,j:integer; begin bit:=TBitmap.Create; If OpenDialog1.Execute then begin bit.LoadFromFile(OpenDialog1.FileName); for i:=0 to N do for j:=0 to N do if bit.Canvas.Pixels=clWhite then LABIRINT:=BLANK else LABIRINT:=WALL; bit.Free; ... end; end; ...

Генерация изображения:

Var N:integer=600; LABIRINT:array of integer; ... procedure genBitmap; var bit:TBitmap; i,j:Integer; begin bit:=TBitmap.Create; bit.Width:=N+1; bit.Height:=N+1; for i:=0 to N do for j:=0 to N do begin if LABIRINT=BLANK then bit.Canvas.Pixels:=clWhite // else if LABIRINT=WALL then bit.Canvas.Pixels:=clBlack else bit.Canvas.Pixels:=clRed; end; bit.SaveToFile("tmp.bmp"); bit.Free; end; ...

Для начала, необходимо пересохранить изображение, как монохромный bmp, для того, чтоб иметь 2 цвета белый или черный. Если присмотреться к лабиринту, то он имеет стенку толщиной в 2 пикселя, а дорогу толщиной в 4 пикселя. Идеально было бы сделать, чтоб толщина стенки и дороги была 1 пиксель. Для этого необходимо перестроить изображение, разделить изображение на 3, то есть удалить каждый 2рой и 3тий, ряд и столбик пикселей из рисунка (на правильность и проходимость лабиринта это не повлияет).

Подготовленный рисунок:

Ширина и высота изображения: 1802 пикселя.

1. Используем функцию сканирования изображения.
2. Перестраиваем изображение:

Var N:integer=1801; LABIRINT:array of integer; ... procedure rebuildArr2; var i,j:integer; begin for i:=0 to ((N div 3)) do for j:=0 to ((N div 3)) do LABIRINT:=LABIRINT; N:=N div 3; end; ...

3. Генерируем перестроенное изображение.

Результат работы процедуры:

Ширина и высота изображения: 601 пиксель.

И так, у нас есть изображение лабиринта нужного вида, теперь самое интересное, поиск всех вариантов прохождения лабиринта. Что у нас есть? Массив с записанными значениями WALL - стена и BLANK - дорога.

Была одна неудачная попытка найти прохождение лабиринта с помощью волнового алгоритма. Почему неудачная, во всех попытках данный алгоритм приводил к ошибке «Stack Overflow». Я уверен на 100%, что используя его, можно найти прохождение, но появился запал придумать что-то более интересное.

Идея пришла не сразу, было несколько реализаций прохождения, которые по времени, работали приблизительно по 3 минуты, после чего пришло озарение: «а что, если искать не пути прохождения, а пути которые не ведут к прохождению лабиринта и помечать их как тупиковые».

Алгоритм такой:
Выполнять рекурсивную функцию по всем точкам дорог лабиринта:
1. Если мы стоим на дороге и вокруг нас 3 стены, помечаем место где мы стоим как тупик, в противном случае выходим из функции;
2. Переходим на место которое не является стенкой из пункта №1, и повторяем пункт №1;

Программная реализация:

Var N:integer=600; LABIRINT:array of integer; ... procedure setBlankAsDeadblockRec(x,y:integer); var k:integer; begin k:=0; if LABIRINT=blank then begin if LABIRINT<><><><>BLANK then k:=k+1; if k=4 then LABIRINT:=DEADBLOCK; if k=3 then begin LABIRINT:=DEADBLOCK; if LABIRINT=BLANK then setBlankAsDeadblockRec(x-1,y); if LABIRINT=BLANK then setBlankAsDeadblockRec(x,y-1); if LABIRINT=BLANK then setBlankAsDeadblockRec(x+1,y); if LABIRINT=BLANK then setBlankAsDeadblockRec(x,y+1); end; end; end; procedure setDeadblock; var i,j:integer; begin for i:=1 to N-1 do for j:=1 to N-1 do setBlankAsDeadblockRec(i,j); end; ...

Заключение

Я получил «полный» рабочий алгоритм, который можно использовать для поиска всех прохождений лабиринта. Последний по скорости работы превзошел все ожидания. Надеюсь моя маленькая работа, принесет кому-то пользу или подтолкнет к новым мыслям.

Программный код и пройденный лабиринт:

//Прошу не бить ногами за использованный язык программирования. unit Unit1; interface uses Windows, Graphics, Forms, Dialogs, ExtCtrls, StdCtrls, Controls, Classes; const WALL=-1; BLANK=-2; DEADBLOCK=-3; type TForm1 = class(TForm) Button1: TButton; OpenDialog1: TOpenDialog; procedure Button1Click(Sender: TObject); private { Private declarations } public { Public declarations } end; var Form1: TForm1; N:integer=600; LABIRINT:array of integer; implementation {$R *.dfm} procedure genBitmap; var bit:TBitmap; i,j:Integer; begin bit:=TBitmap.Create; bit.Width:=N+1; bit.Height:=N+1; for i:=0 to N do for j:=0 to N do begin if LABIRINT=BLANK then bit.Canvas.Pixels:=clWhite // else if LABIRINT=WALL then bit.Canvas.Pixels:=clBlack else bit.Canvas.Pixels:=clRed; end; bit.SaveToFile("tmp.bmp"); bit.Free; end; procedure rebuildArr2; var i,j:integer; begin for i:=0 to ((N div 3)) do for j:=0 to ((N div 3)) do LABIRINT:=LABIRINT; N:=N div 3; end; procedure setBlankAsDeadblockRec(x,y:integer); var k:integer; begin k:=0; if LABIRINT=blank then begin if LABIRINT<>BLANK then k:=k+1; if LABIRINT<>BLANK then k:=k+1; if LABIRINT<>BLANK then k:=k+1; if LABIRINT<>BLANK then k:=k+1; if k=4 then LABIRINT:=DEADBLOCK; if k=3 then begin LABIRINT:=DEADBLOCK; if LABIRINT=BLANK then setBlankAsDeadblockRec(x-1,y); if LABIRINT=BLANK then setBlankAsDeadblockRec(x,y-1); if LABIRINT=BLANK then setBlankAsDeadblockRec(x+1,y); if LABIRINT=BLANK then setBlankAsDeadblockRec(x,y+1); end; end; end; procedure setDeadblock; var i,j:integer; begin for i:=1 to N-1 do for j:=1 to N-1 do setBlankAsDeadblockRec(i,j); end; procedure TForm1.Button1Click(Sender: TObject); var bit:TBitmap; i,j:integer; begin bit:=TBitmap.Create; If OpenDialog1.Execute then begin bit.LoadFromFile(OpenDialog1.FileName); for i:=0 to N do for j:=0 to N do if bit.Canvas.Pixels=clWhite then LABIRINT:=BLANK else LABIRINT:=WALL; bit.Free; setDeadblock; genBitmap; end; end; end.

Для поиска кратчайшего пути, планируется применить волновой алгоритм к найденным прохождениям лабиринта. Было-бы интересно услышать, какие еще алгоритмы можно применить, для быстрого поиска пути в большом лабиринте?

Разоблачаем! Можно ли пройти этот лабиринт? November 29th, 2014

Вот такая картинка сейчас бродит по всему интернету. Зачастую это сопровождается таким текстом: "В израильской военной разведке есть специальное подразделение, в котором служат юноши и девушки, страдающие разными нарушениями аутического спектра. Аутисты занимаются в основном анализом карт и аэрофотоснимков, появляющихся на экранах компьютеров. В силу особенностей мышления они обращают внимание на мельчайшие подробности, учет которых при подготовке военных операций на местности позволяет не допустить возможных потерь личного состава. Таким образом аутисты-разведчики спасают жизни солдат."

Вы пробовали проходить этот лабиринт?

Давайте выясним подробнее этот вопрос..

еще при упоминании этого лабиринта уточняется, что "Аутист способен обрабатывать визуальную и текстовую информацию в несколько раз быстрее, чем человек, не страдающий заболеваниями аутического спектра. Эта их особенность оказалась незаменимой в хайтеке. В датской компании Specialisterne, специализирующейся на технологическом консультировании, 75 процентов работников - аутисты и люди, у которых диагностирован синдром Аспергера, также относящийся к аутическому спектру. От обычных работников они отличаются невероятным вниманием к деталям, сверхчеловеческой сосредоточенностью, способностью быстро обрабатывать огромные массивы информации. Эти умения особенно полезны для тестировщиков программ. Качество работы аутистов, занимающихся этой работой, в несколько раз выше, чем качество работы обычных людей. Аутисты могут проверить техническую документацию на 4000 страниц в 10 раз быстрее обычных людей и не пропустить ни одной ошибки."

Но оставим в стороне аутистови выясним в конце концов как можно пройти этот лабиринт! А вот как...

Задача нерешаема! У нас 3 комнаты с нечетным количеством дверей (аналогия с рисунками "не отрывая карандаша"). Что бы задача имела решение необходимо, что бы было не более 2 точек(в нашем случае комнат) с нечетным количеством линий (в нашем случае проходов)

Если построить граф этого лабиринта, то мы увидим, что это Эйлеров путь, так как у него 3 вершины с нечётным числом рёбер (дверей), а для выполнения условий теста их может быть только две.

Проблема семи мостов Кёнигсберга или Задача о кёнигсбергских мостах (нем. Königsberger Brückenproblem ) - старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга, не проходя ни по одному из них дважды. Впервые была решена в 1736 году немецким и русским математиком Леонардом Эйлером.

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через реку Преголя), не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог.

В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. Ответ был «нельзя».

На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города - точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:

• Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.


• Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.


• Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

Созданная Эйлером теория графов нашла очень широкое применение в транспортных и коммуникационных системах (например, для изучения самих систем, составления оптимальных маршрутов доставки грузов или маршрутизации данных вИнтернете).

В 1905 году был построен Императорский мост, который был впоследствии разрушен в ходе бомбардировки во время Второй мировой войны. Существует легенда о том, что этот мост был построен по приказу самого кайзера, который не смог решить задачу мостов Кёнигсберга и стал жертвой шутки, которую сыграли с ним учёные умы, присутствовавшие на светском приёме (если добавить восьмой мост, то задача становится разрешимой). На опорах Императорского моста в 2005 году был построенЮбилейный мост. На данный момент в Калининграде семь мостов, и граф, построенный на основе островов и мостов Калининграда, по-прежнему не имеет эйлерова пути

Вот еще такой вариант решения предлагал xlazex

Посмотрим на картинку1: окружим квадратами каждую отдельную часть, исключим "лишние" точки, т.е. те точки, использование которых повысило бы возможное количество путей, и исключение которых не повлияет на количество дверей, пройденных линией и замкнутость контура. За начало пути возьмем, к примеру, точку 2 .
Посмотрим на картинку2: на ней я изобразил тот же контур, но так, чтобы были виднее связи начальной точки с последующими. На изображении явно видно, что часть контура, обведенная синим цветом не может быть единожды замкнута, т.е. даже если бы эта часть контура была единственна, то не существовало бы путей, по которым можно было бы построить замкнутую линию.
Итог: задача не имеет решения в двумерной системе координат.