IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Лабиринт, интеллектуальная Задача
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 5
Пол: Мужской

Репутация: -  0  +


ЛЮДИ ОТКЛИКНИТЕСЬ!!! Помогите пожалуйста с задачей. Не могу написать его на паскале. Имеется алгоритм
Матрица размера N*M определяет некоторый лабиринт. B матице элемент 1 обозначает стену, а 0 определяет свободное место. В первой строке матрицы определяются входы x(i), а в последней выходы y(i), i=1,..,k, которые должны быть нулевыми элементами.

Необходимо определить, можно ли

а) провести k человек от входа x(i) до выхода y(i) соответственно, i=1,..,k, таким образом, чтобы каждое свободное место посещалось не более одного раза.

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

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

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 3.12.2021 4:43
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name