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

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

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

> Лабиринт, ПОмогите пожалуйста с лабиринтом
keng
сообщение 11.09.2011 11:42
Сообщение #1





Группа: Пользователи
Сообщений: 8
Пол: Мужской
Реальное имя: Андрей

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


Здравствуйте!Помогите пожалуйста с курсовым по Паскалю!Задание примерно состоит в том чтобы сделать программу которая ищет выход из лабиринта.Самому простейшему варианту буду очень рад(желательно с комментариями)Заранее спасибо!
PS Очень оЧЕНЬ надо А я в Паскале не бум бум)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
Lapp
сообщение 14.09.2011 4:00
Сообщение #2


Уникум
*******

Группа: Модераторы
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

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


На всякую гениальную программу найдется еще более гениальная! - (С) Lapp ))
Вот, набросал еще один вариантик простейшего лабиринта (главным образом потому, что лень было разбираться с тем)).

На квадратной сетке, каждая ячейка есть либо стена, либо свободное пространство.
Фомируется случайным образом с заданной плотностью стен.
Принцип - правило одной руки (будем считать - левой). Реализовано оно тут примерно так.

Лабиринт - это массив m на n. Начальные значения задаются так:
0 - свободное пространство (а также - счетчик, сколько раз были на этой клетке).
Wall (тут равно 8) - стена.
При прохождении "свободное пространство" принимает значения от 0 до 4, увеличиваясь при каждом заходе на клетку. Суть в том, что если мы заходим на некоторую клетку более 4 раз (на самом деле, это может случиться только с начальной клеткой) - это значит, что лабиринт непроходим (т.к. мы уже перебрали все четыре пути, ведущие из нее).

Вот алгоритм:
1. Сначала входим на начальную клетку (она должна быть свободной) с произвольного направления (его можно выбирать случайно, но у меня просто постоянное).
2. Поворачиваемся налево.
3. Делаем шаг вперед.
4. Если оказались внутри стены (не пугайся, можешь считать, что ходишь по нарисованному лабиринту)), то поворачиваемся назад и переходим к п.3.
5. Если оказались в на свободном пространстве - проверяем, не финиш ли это (B).
6. Если финиш - подготавливаем сообщение и выходим из цикла.
7. Если не финиш - смотрим, сколько раз тут были (значение массива).
8. Если уже были тут 3 раза (то есть пришли в четвертый раз) - значит, лабиринт непроходим (подготавливаем сообщение и выходим из цикла).
9. Если меньше 3 раз, то увеличиваем значение массива.
10. Переходим к п.2

При плотности заполнения 35% получаются довольно интересные конфигурации иногда )). Вот, например, конфигурация непроходимая:
Running "c:\...\pas\fp\fp110911_keng\fp110911_keng_lapp-3.exe "
██████████████████████████████████████████████████████████████
█A█ ██ █ █ █ ██ █ ██ █ ██ ████ █ █ █ █ █ █ █
█ █ ██ █ █ █ ██ █ █ █ █████ █ █ ██
█ █ ██ █ █ ██ █ ███ █ █ █ █ ██ █ █
█ █ ███ ██ ██ █ ███ ██ █ ██ █ █ █ ██ █
███ █ ██████ ██████ █ █ █ ██ █ █ █ █ █ █ █
█ █ ██ █ █ █ █ █ █ █ ██ ██ ██ █ ██ █
█ █ █ █████ █ ██ ███ ██ ██ █ ██ █ █ █ ██
█ █ █ █ █ █ █ █ ███ █ ██ █ █ ██ █ █
█ ███ ███ █████ ██ █ █ █ █ █ █
██████ █ ████ █ █ █ ██ █ ██ ██ █ █ ██ █ ██
█ █ █ ██ █ █ █ █ ███ █ █ ██ ██ █
█ █ █ █ █ ██ █ █ █ ██ █ █ █ ██
█ █ █ █ ██ █ █ █ █ █ ███ █ █ ███ █ ██ █ █ █
█ █ ██ █ █ ██ ██ █ █ █ █ ██ █ █ █ █ █
█ █ ██ ██ ███ █ █ ██ █ █ ██ ███ █ █ ██ ███
███ █ █ █ ██ █ ██ █ █ ███ ██ █
███ █ ██ █ █ ███ █ ██ █ █ █ █ ██
█ █ █ █ ███ █ █ ████ █ █ █ █ █ █ █ █
█ █ ██ ███ █ █ ██ █ ██ ██ █ █ ███ █
██████ █ █ ██ █ ██ ████ █ █ █ ████ ██ █ █
███ █ █ █ █ ██ ██ █ █ █ ██ █ ██
█ █ ██ █ ███ █ █ ██ █ █ █ █ █
██ █ █ █ █ █ ██ ███ █ █ █ ████ ███ ██
███ ██ ██ ██ ██ █ █ █ █ █ ██ █ █ ██ █ B█
██████████████████████████████████████████████████████████████

No way.. :-( The mean Minotaur got me..

██████████████████████████████████████████████████████████████
█A█**██****█******█*█ ██ █**██*█**██**████*█***█ █***█ █ █ █
█***█****██** █ *█**█ ██***█*******█*█*****█████***█ █ ██
█*█*** ****██ █ *█***██*** *█*███***█**█* ****█***█*██ █*█
█***█ ███ ██ ██ ***█**███***██***█******* ██ **█**█***█ ██*█
███*█ ██████ ██████ *█****█******* █ ██ █*█ █*█****█*█*█
█***█ *** ██ █ █ ***█**█*█*█* █ ██ ██ *██****█*██***█
█* █ **█* █████ █ *██***███*** ██ ██ █*██* █**█ █**██
█*█ **█**█ █ █ █ █ ***███****█**██*** █**█**██ **█****█
█*****███* ███ █████ ***██**█*█****█* *█** █ ******█
██████**█*████ █ █ ***█ **██*█*██*██** █ *█* ██ *█**██
█**█*█****██ █ **█* **█*█***███*█** ****█** ██ **██ █
█****** █ █ █ *█***** *██***█******█* *█**██** █ █*█ ██
█**█* █ █ ██ █***█*█*█****█**███*█**█** **███*█*██ █ **█ █
█**█*██ █ *█*██**██**█ █****█***█*██ *****█*█ █****█ █
█*█**██ ██*███*****█**█***██*█*█**██ ███*█**█ *██**███
███* █ █ **█**██ **█***██****█** █ *** ███***██ █
███* █*** ██ ***█*******█**███*█*██** █ █ █ **█ ██
█***█**█* █ *███*█*█*████*█*******█*█ █ █ ***█ █ █
█*****█***********██*███ █ █*██****█*██** ██ █ █*███ █
██████***█**█*██*█***██*████****█*█****█**████ ██ ******█ █
███***█**█***█****█*****██****██ █*** **█* █*** **██***█ ██
█****█***██***█*****███**█* **█ ██**********█*****█**█***█ █
██*█*█* **█*█**█***██****** **███ █*█****█***████*****███ ██
███******██**██***██ ██*█*****█ █ █***█**██**█ █****██ █ B█
██████████████████████████████████████████████████████████████

- мы тут описали полный круг и вернулись в точку входа А.

А вот эта - проходимая, заканчивается в B. Довольно интересный случай, советую проследить детально )).
Running "c:\...\pas\fp\fp110911_keng\fp110911_keng_lapp-3.exe "
██████████████████████████████████████████████████████████████
█A ██ ██ █ ██ █ █ █ █ █ ███ ██ ██ █ █ ███
█ ██ █ █ █ █ █████ █ █ ██ █ █ █ ██ █
█ ███ █ ███ █ █ ██ ██ █ ██ █████ ██████ █
█ █ ███ ██ █ █ █ █ █ █ █ ██ █ █ █ █ █
███ ██ █ ███ █ █ ██ ██ █ ██ █ █ █ █
██ █ █ █ █ █ █ █ █████ █ █ █ ██ █
████ █ █ █ █ █ █ █ ██ █ █ █ █ ████
█ █ █ █ ██ ██ █ ███ █ ██ █ ██ █ █ █ ██ █
█ ███ █ █ █ █ ██ ████ █ ██ █ ██ █ █ ██
███ █ █ ██ ██ █ ████ ██ ██ █ ███ █ █ ███
██ █ ██ █ █ █ ███ ██ █ █ █ ██ █ █████ █ ██
█ █ ██ █ ██ █ █ █ ██ █ █ █ ██ █ █ ███
█ █ █ █ █ ██ ██ █ █ █ █ █ ██ █ ███ █ ██ █ █
██ █ ██ █ █ ██ █ ██ ██ █ █ ██ █ ██ ███████ ████
█ █ ███ █ █ █ █ █ █ █ █ ███ █ █ █ ███
█ █ █ █ █ ██ ██ █ ██ █ ██ █ █ █ █ █
██ ██ █ █ ███ ██ ██ ██ █ ██
█ ███ █ █ █ ██ █ ██ █ █ ████ ██ ███ █ ██
█ █ █ █ █ █ █ █ ███ █ ███ ██ █ ██ █ ██
█ █████ █ ██ ████ █ █ █ █ █
█ ██ █ ██ ██ █████ █ █ █ █ █ █ █
█ ██ █ ██ ██ ███ █ █ █ ██ █ █ ██ █ ██
█ ██ ██ ███ █ █ ██ █ ███ █ ███ █ █
█ █ █ █ █ █ █ █ ██ █ █ ██ ███ █ █ ██ █ ██ █ █B█
██████████████████████████████████████████████████████████████

Escaped! :-) Hei stupid Minotaur - kiss my ass!

██████████████████████████████████████████████████████████████
█A****██****██**█***██ █****█******█*█**█**███*██ ██ █ █ ███
█ ██*█ █*█*█*******█████** ****█***█****██*******█ █ █ ██ █
█ *███**█**███ █**█**██***██***█*** *██*█████***██████ █
█ █*███**██* █ █ **█*█***█*█*█*██********█****█*******█ █ █
███ *██******█ ███ *****█****█ ██ ██*█**██**█ **█ █ █
██ █*█** █ █ █ *█ █ █████*****█ █ **█*██ █
████*** █ █ █ █ ******█ █ █ ██**█*█** █****█****████
█ █ █ █ ██ ██ █ **███***█ ██ █***██*█****█***█*██ █
█ ███ █ **█**█*█*██ ████*█***██*█*██****█ █ ██
███ █ █ ██ *██*█****████ ██ ██**█***███*** █**█ ███
██ █ ██ █ █ █ ███*██**█**█ █**██ █ █████****** **█ ██
█ █ ██ █****██*█*█*█***██ █ █ █* *██***█**█ ███
█ █ █ █ █ ██ ***██*█**█*█ █ █ ██ █****███*█*██ █ █
██ █ ██ █ █ ██ █ ██ ██****█**█*██ █ ██*███████*****████
█ █ ███ █ █ █ █***█***█ █ █**███*█ █***█*███
█ █ █ █ █ ██ ██ █ *****██ █ ██**█***█ █****█ █
██ ██ █ █ *███ ██ ██**** **██** █**██
█ ███ █ █ █ ██ █ ██ █ █***████*██*** *███* █ *██
█ █ █ █ █ █ █ █ ███ █ *███****██*█ **██* █ *██
█ █████ █ ██ ████ **█*** █**** ****█ █ **█
█ ██ █ ██ ██ █████ **█**█ █ █ █ █ **█
█ ██ █ ██ ██ ███ *█**█ █ ██ █ █ ██ █ *██
█ ██ ██ ███ █ █ ██ *** █ ███ █ ███ █**█
█ █ █ █ █ █ █ █ ██ █ █ ██ ███ █ █ ██ █ ██ █ █B█
██████████████████████████████████████████████████████████████



А вот код. Пока без комментов )).
Давай договоримся так: попробуй сначала разобраться сам (используя алгоритм, приведенный выше). Можешь сделать свои комменты - я посмотрю, правильно или нет. Если не сможешь разобраться - задавай вопросы.
// The Simplest Maze Ever
// Wall Follower, or one-hand rule
// by Lapp, forum.pascalnet.ru
// Sep 13, 2011

const
m= 24;
n= 60;
x1= 1;
y1= 1;
x2= m;
y2= n;
Wall= 8;
Chars: array[0..Wall] of char= ' **** '+Chr(219);

var
Maze: array[1..m,1..n] of integer;

procedure Show;
var
i,j: integer;
begin
WriteLn;
for i:=0 to m+1 do begin
for j:=0 to n+1 do begin
if (i=0) or (i>m) or (j=0) or (j>n) then Write(Chr(219))
else if (i=x1) and (j=y1) then Write('A')
else if (i=x2) and (j=y2) then Write('B')
else Write(Chars[Maze[i,j]])
end;
Writeln
end;
WriteLn
end;

var
x,y,dx,dy,b: integer;
s: string;

begin
Randomize;
for x:=1 to m do for y:=1 to n do
if Random(100)<36 then Maze[x,y]:= Wall else Maze[x,y]:= 0;
Maze[x1,y1]:= 0;
Show;
x:= x1;
y:= y1;
dx:= 0;
dy:= 1;
repeat
if (x<1) or (y<1) or (m<x) or (n<y) or (Maze[x,y]=Wall) then begin
dx:= -dx;
dy:= -dy
end
else if (x=x2) and (y=y2) then begin
s:= 'Escaped! :-) Hei stupid Minotaur - kiss my ass!';
break
end
else if Maze[x,y]=4 then begin
s:= 'No way.. :-( The mean Minotaur got me..';
break
end
else begin
Inc(Maze[x,y]);
b:= dx;
dx:= -dy;
dy:= b
end;
x:= x+dx;
y:= y+dy
until false;
Writeln(s);
Show;
Readln
end.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме
keng   Лабиринт   11.09.2011 11:42
TarasBer   1. Изучи основы Паскаля (время у тебя есть). 2. Из...   11.09.2011 12:28
Lapp   сделать программу которая ищет выход из лабиринта....   12.09.2011 3:36
keng   keng, давай начнем с описания лабиринта. Уточни ...   12.09.2011 16:04
TarasBer   Ну на один вопрос ты ответил, ладно. Остался второ...   12.09.2011 16:28
keng   У меня есть некоторые мысли но нужно в одну их соб...   13.09.2011 10:15
TarasBer   Надо дописать в начало процедуры вот это, иначе бу...   13.09.2011 11:26
keng   Да оставил если не сдам отчислят(( А как это все о...   13.09.2011 11:44
TarasBer   Ну пишешь всё это и в конце пишешь begin xk :=...   13.09.2011 12:57
keng   uses wincrt; label 1,2,3; var f:text; i,j,k,xn,jn,...   13.09.2011 13:07
Гость   uses CRT; const mx=100; nx=100; Left=1; Rig...   13.09.2011 14:24
Lapp   Я попробую сделать свой Ловлю на слове ). Я думаю...   13.09.2011 22:49
Lapp   [color=#009900]На всякую гениальную программу найд...   14.09.2011 4:00
keng   Все таки вот этот меня зацепил чем то)Я попробывал...   15.09.2011 10:07
TarasBer   > //дир в будующем является const Чего? Проце...   15.09.2011 10:19
keng   TarasBer Спасибо!Теперь это мне понятно!А ...   15.09.2011 10:59
Lapp   Послушай, keng, это же совсем (ну, хорошо, не совс...   16.09.2011 4:52


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

 



- Текстовая версия 21.06.2025 14:38
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"