немного выдержка из книги
Глава 4
Лабиринты
В лабиринте у вас, по крайней мере, есть цель.
Евгений Кащеев
Мне нравится эта тема. С одной стороны, она занимательна, с другой —
полезна (я надеюсь, что вы найдете не одно и не два применения
алгоритмам, описанным в этой части книги), а с третьей — даже научна.
Лабиринты, выражаясь математическим языком — это графы; все алгоритмы,
которые мы рассмотрим, соответственно, являются алгоритмами на графах.
Графам же посвящена целая теория в математике (она так и называется:
теория графов). Недаром два алгоритма, с которыми вы познакомитесь в
этой главе, носят имена Прима (Prim) и Краскала (Kruskal) — очень
известных в теории графов людей.
Итак, сейчас мы займемся лабиринтами. Если говорить более конкретно, в область наших интересов входят следующие задачи:
- определить, что такое лабиринт и как представить его в памяти компьютера;
- договориться, что значит «решить» лабиринт и как это сделать;
- выяснить, как лабиринт может быть создан компьютером автоматически.
Представление лабиринтов в памяти
Толковый словарь русского языка определяет лабиринт как «запутанную
сеть дорожек, ходов, сообщающихся друг с другом помещений». Пожалуй, это
определение слишком неконкретное и чересчур общее для наших целей.
Сразу скажу, что наши лабиринты — плоские (двумерные, если угодно),
поэтому их можно легко нарисовать на бумаге. Кроме того, все помещения
(их обычно называют локациями) будут квадратными, а сам лабиринт
(естественно) — прямоугольным. У каждого такого помещения есть не более
четырех соседних, и в каждое соседнее помещение может вести проход (а
может и не вести — в этом случае там будет «стена»). Думаю, проще всего
посмотреть на пример (рис. 4.1).
мое дело программы писать а не книгу цитировать тем более вы можете ее сами прочесть скажем на
http://www.piter-press.ru/attachment.php?barcode=978594723853&at=exc&n=0
В каждой локации лабиринта нас интересует информация о стенах/проходах. В
локации может существовать от одной до четырех стен (сверху, снизу,
слева и справа). Поэтому разумно задавать локацию записью:
type Location=record
left_wall,up_wall:Boolean;
end;
type Maze=array of array of Location;
procedure LoadMaze(var TheMaze : Maze; Name : string); //загрузить лабиринт
var
f:TextFile; //файл с описанием лабиринта
Height, Width:Integer;//высота и ширина лабиринта
x,y:Integer;//текущая локация
lw,uw:Integer; //временные переменные
begin
AssignFile(f,'Name.txt'); //открыть файл
Reset(f);
ReadLn(f,Width,Height);//прочитать высоту и ширину
SetLength(TheMaze,Width+1,Height+1);//изменить размер лабиринта
for y:=0 to Height do //цикл по всем локациям
for x:=0 to Width do
if (y=Height)or(x=Width) then //если локация-служебная
begin
TheMaze[x,y].left_wall := true; //обе стены существуют
TheMaze[x, y].up_wall := true;
end
else
begin //иначе считываем
ReadLn(f, uw, lw); // из файла
TheMaze[x, y].left_wall := Boolean(lw);//прочитанное целое
TheMaze[x, y].up_wall := Boolean(uw);//число надо привести
end; //к типу Boolean
CloseFile(f);
end; //закрыть файл
procedure SaveMaze(TheMaze : Maze; Name : string); //сохранить лабиринт
var
f:TextFile; // файл с описанием лабиринта
Height, Width : Integer;//высота и ширина
x, y : Integer;//координаты текущей локации
begin
AssignFile(f, 'Name.txt');//открыть файл
Rewrite(f);//для записи
Height := High(TheMaze[0]);//определяем высоту
Width := High(TheMaze);//и ширину лабиринта
WriteLn(f, Width, ' ', Height);//запись в файл высоты и ширины
for y := 0 to Height - 1 do // запись данных локаций }
for x := 0 to Width - 1 do
WriteLn(f, Integer(TheMaze[x, y].up_wall), ' ',
Integer(TheMaze[x, y].left_wall));
CloseFile(f); //закрыть файл
end;
рекурсивный обход лабиринта
Волновая трассировка
исходник программы на Delphi 7
/45_labirint.rar
