Листинг файла Unit1. cpp

// ---------------------------------------------------------------------------

#include <vcl. h>

#pragma hdrstop

#include "Unit1. h"

#include "Unit2. h"

// ---------------------------------------------------------------------------

#pragma package (smart_init)

#pragma resource "*. dfm"

TForm1 *Form1;

// ---------------------------------------------------------------------------

__fastcall TForm1:: TForm1 (TComponent* Owner)

: TForm (Owner)

{

}

// ---------------------------------------------------------------------------

void __fastcall TForm1:: Image1Click (TObject *Sender)

{

Form1->Visible = false;

Form2->Visible = true;

Form2->Show ();

Form2->SetFocus ();

Form2->FormClick (Form2);

}

// ---------------------------------------------------------------------------

Листинг файла Unit2. cpp

// ---------------------------------------------------------------------------

#include <vcl. h>

#pragma hdrstop

#include "Unit1. h"

#include "Unit2. h"

// ---------------------------------------------------------------------------

#pragma package (smart_init)

#pragma resource "*. dfm"

TForm2 *Form2;

// структура одной комнаты

struct komnata{

// является ли комната проходной или нет

bool stena;

// сокровища

int sokrovihe;

// номер комнаты в находимом пути

int number;

};

// структура узла дерева (комнаты), строящегося для нахождения пути

struct leaf{

// точка, ее координаты - это номер комнаты

// по горизонтали и вертикали

TPoint id;

// сколько денег накапливается до этой комнаты

int mone;

// указатель на предыдущую комнату

leaf* parent;

// указатели на соседние комнаты

leaf** kids;

// конструктор узла

leaf () {

// выделяется память для соседних комнат

kids = new leaf* [4];

for (int i=0; i<4; i++)

kids [i] =NULL;

}

bool IsVisited (int x, int y, leaf* obj);

void SetNewLeaf (leaf *obj, int n);

void Tracing (leaf* obj, int n);

void GrowTree (TPoint p, leaf* obj);

};

// размерность лабиринта

const int N = 15;

// массив из комнат

komnata a [N] [N];

// максимальное значение накопленных сокровищ

int max = 0;

// режим отображения информации

int info = 0;

// указатель на корень поискового дерева

leaf* root = NULL;

// точки - координаты комнат входа и выхода

TPoint A,B;

// был ли запущен процесс поиска пути

bool process = false;

// был ли прерван процесс поиска пути

bool newprocess = false;

// графический буфер для отрисовки лабиринта

Graphics:: TBitmap *buffer = new (Graphics:: TBitmap);

// ---------------------------------------------------------------------------

__fastcall TForm2:: TForm2 (TComponent* Owner)

: TForm (Owner)

{

}

// ---------------------------------------------------------------------------

// функция создания лабиринта

void CreateLabirint ()

{

// создаем везде стены

for (int i=0; i<=N; i++)

for (int j=0; j<=N; j++) {

a [i] [j]. stena = true;

a [i] [j]. sokrovihe=random (99) +1;

a [i] [j]. number=0; }

// текущая комната и направление движения

int x,y,c;

// делаем N/2 циклов создания коридоров

for (int i=0; i<=N/2; i++) {

// выбираем случайную комнату внутри лабиринта

x = random (N-2) +1;

y = random (N-2) +1;

// выбираем случайное направление движения

c = random (4);

// выбираем случайное количество поворотов коридора

for (int d = random (3) +2; d>=0; d--) {

// выбираем случайное количество комнат до поворота

for (int k = random (3) +2; k>=0; k--) {

switch (c) {

// переходим в одну из четырех сторон

case 0: x++; break;

case 1: y++; break;

case 2: x--; break;

case 3: y--; break; }

// самые крайние комнатамы не делаем

if (x<=0||y<=0||x>=N-2||y>=N-2) break;

a [x] [y]. stena = false; }

// переходим на другое направление

c = (c+1) %4; }}

// случайно выбираем комнату, от которой будем строить путь

A. x=0; A. y=0;

while (A. x==0&&A. y==0)

if (a [x=random (N)] [y=random (N)]. stena==false)

{A. x=x; A. y=y; };

// случайно выбираем комнату, до которой будем строить путь

B. x=0; B. y=0;

while (B. x==0&&B. y==0)

if (a [x=random (N)] [y=random (N)]. stena==false)

{B. x=x; B. y=y; };

}

// функция отрисовки лабиринта

void Draw ()

{

// размеры сетки лабиринта по горизонтали и вертикали

int n=buffer->Height/N;

int m=buffer->Width/N;

// закрашиваем нарисованное до этого

buffer->Canvas->Brush->Color = clWhite;

buffer->Canvas->Pen->Color = clWhite;

buffer->Canvas->Rectangle (0,0,buffer->Width, buffer->Height);

// проходим двойным циклом по массиву комнат

for (int i=0; i<N; i++)

for (int j=0; j<N; j++)

// если это стена, то закрашиваем ее черным прямоугольником

if (a [i] [j]. stena) {

buffer->Canvas->Pen->Color = clBlack;

buffer->Canvas->Brush->Color = clBlack;

buffer->Canvas->Rectangle (i*m,j*n, i*m+m,j*n+n);

}else{

// если это комната, то в зависимости от режима отображения рисуем по-разному

switch (int inf=info) {

// выводим полную информацию:

case (0): {

buffer->Canvas->Brush->Color = clWhite;

buffer->Canvas->Font->Color = clRed;

// если это комната входа, то закрашиваем ее желтым

if (i==A. x&&j==A. y) {

buffer->Canvas->Brush->Color = clYellow;

buffer->Canvas->Pen->Color = clYellow;

buffer->Canvas->Font->Color = clBlack;

buffer->Canvas->Rectangle (i*m,j*n, i*m+m,j*n+n); }

// если это комната выхода, то закрашиваем ее голубым

if (i==B. x&&j==B. y) {

buffer->Canvas->Brush->Color = clSkyBlue;

buffer->Canvas->Pen->Color = clSkyBlue;

buffer->Canvas->Font->Color = clBlack;

buffer->Canvas->Rectangle (i*m,j*n, i*m+m,j*n+n); }

// выводим в верхнем левом углу количество монет, которое можно забрать в этой комнате

buffer->Canvas->TextOutA (i*m+1,j*n+1, IntToStr (a [i] [j]. sokrovihe));

// если через эту комнату не ведет путь, то уходим

if (a [i] [j]. number==0) continue;

// иначе запоминаем номер комнаты в пути

String s=IntToStr (a [i] [j]. number);

// запоминаем его размеры при отрисовке

int I=i*m+m-buffer->Canvas->TextWidth (s);

int J=j*n+n-buffer->Canvas->TextHeight (s);

buffer->Canvas->Brush->Color = clLime;

buffer->Canvas->Font->Color = clBlack;

// и выводим его на зелёном фоне

buffer->Canvas->TextOutA (I,J,s);

break; }

// режим отображения найденного пути

case 1: {

buffer->Canvas->Brush->Color = clLime;

buffer->Canvas->Pen->Color = clBlack;

buffer->Canvas->Font->Color = clBlack;

// увеличиваем размер шрифта

buffer->Canvas->Font->Size+=3;

// запоминаем размеры надписи

String s=IntToStr (a [i] [j]. number);

int I=buffer->Canvas->TextWidth (s);

int J=buffer->Canvas->TextHeight (s);

// рассчитываем ее координаты, чтобы вывести посередине

int x=i*m+ (m-I) /2;

int y=j*n+ (n-J) /2;

// если эта комната не включена в путь то закрашиваем ее

if (a [i] [j]. number==0)

buffer->Canvas->Brush->Color = clWhite;

buffer->Canvas->Rectangle (i*m,j*n, i*m+m,j*n+n);

// иначе выводим ее номер от входной по порядку

if (a [i] [j]. number! =0)

buffer->Canvas->TextOutA (x,y,s);

buffer->Canvas->Font->Size-=3;

break; }

// вывод информации о сокровищах

case 2: {

buffer->Canvas->Font->Color = clBlack;

buffer->Canvas->Brush->Color = clYellow;

buffer->Canvas->Pen->Color = clBlack;

buffer->Canvas->Font->Size+=3;

// запоминаем размеры выводимой надписи

String s=IntToStr (a [i] [j]. sokrovihe);

int I=buffer->Canvas->TextWidth (s);

int J=buffer->Canvas->TextHeight (s);

int x=i*m+ (m-I) /2;

int y=j*n+ (n-J) /2;

// если комната не включена в путь, то фон делаем белым

if (a [i] [j]. number==0)

buffer->Canvas->Brush->Color = clWhite;

buffer->Canvas->Rectangle (i*m,j*n, i*m+m,j*n+n);

buffer->Canvas->TextOutA (x,y,s);

buffer->Canvas->Font->Size-=3; }

}}

// копируем все нарисованное из буфера в окно программы

Form2->Canvas->CopyRect (TRect (0,0,Form2->Width,Form2->Height),

buffer->Canvas,TRect (0,0,Form2->Width,Form2->Height));

}

// рекурсивная функция проверки посещения комнаты

bool leaf:: IsVisited (int x, int y, leaf* obj)

{

// если координаты этой комнаты не совпадают с координатами искомой

if (obj! =NULL)

// и не совпадают с координатами предыдущей комнаты, то возвращаем ложь

return (obj->id. x==x&&obj->id. y==y) ||IsVisited (x,y,obj->parent);

else return false;

}

// функция установки нового листа

void leaf:: SetNewLeaf (leaf *obj, int n)

{

// выделяем память

obj->kids [n] =new leaf;

// назначаем предыдущую комнату в дереве посещений

obj->kids [n] - >parent = obj;

}

// реверсивная функция разметки пути

void leaf:: Tracing (leaf* obj, int n)

{

if (obj! =NULL) {

// отмечаем комнату номером n

a [obj->id. x] [obj->id. y]. number=n;

// и предыдущую комнату номером n-1

Tracing (obj->parent,n+1); }

}

// функция установки номеров всех комнат в 0

void InNul ()

{

for (int i=0; i<N; i++)

for (int j=0; j<N; j++)

a [i] [j]. number=0;

}

// функция поиска пути в лабиринте

// в процессе создается дерево из комнат

void leaf:: GrowTree (TPoint p, leaf* obj)

{

// обрабатываем системные сообщения приложения: нажатия мыши, клавиш

Application->ProcessMessages ();

// если был переключен режим

// то меняем заголовок

if (info==1)

Form2->Caption="Обрабатывается комната с координатами "+IntToStr (p. x) +","+IntToStr (p. y) +". ";

if (info==2)

if (max! =0)

Form2->Caption="Текущий путь забирает монет: "+IntToStr (max)

+"; через "+IntToStr (a [A. x] [A. y]. number) +" комнат";

else

Form2->Caption="Путь еще не найден";

// записываем суммарное количество забранных монет

if (obj->parent == NULL)

obj->mone=a [p. x] [p. y]. sokrovihe;

else

obj->mone=obj->parent->mone+a [p. x] [p. y]. sokrovihe;

// записываем координаты текущей комнаты

obj->id = p;

// если текущая - это та, которую нам надо было найти

if (p. x==B. x&&p. y==B. y) {

// если мы еще не записывали максимальное количество монет

// или нашли новый максимальный путь

if (max==0||obj->mone>max) {

// записываем количество монет

max=obj->mone;

// обнуляем все комнаты

InNul ();

// записываем путь

Tracing (obj,1);

// отрисовываем

Draw ();

}

// удаляем выделенную память

delete [] obj->kids;

delete obj;

// выходим

return;

}

// если мы не отменяли процесс поиска клавишей Escape

// то добавляем ссылки на соседние комнаты

if (! newprocess) {

if (! a [p. x-1] [p. y]. stena&&! IsVisited (p. x-1,p. y,obj))

SetNewLeaf (obj,0);

if (! a [p. x+1] [p. y]. stena&&! IsVisited (p. x+1,p. y,obj))

SetNewLeaf (obj,1);

if (! a [p. x] [p. y-1]. stena&&! IsVisited (p. x,p. y-1,obj))

SetNewLeaf (obj,2);

if (! a [p. x] [p. y+1]. stena&&! IsVisited (p. x,p. y+1,obj))

SetNewLeaf (obj,3);

// и рекурсивно обрабатываем соседние комнаты

if (obj->kids [0]! =NULL)

GrowTree (TPoint (p. x-1,p. y),obj->kids [0]);

if (obj->kids [1]! =NULL)

GrowTree (TPoint (p. x+1,p. y),obj->kids [1]);

if (obj->kids [2]! =NULL)

GrowTree (TPoint (p. x,p. y-1),obj->kids [2]);

if (obj->kids [3]! =NULL)

GrowTree (TPoint (p. x,p. y+1),obj->kids [3]);

}

// удаляем выделенную память

delete [] obj->kids;

delete obj;

}

// ---------------------------------------------------------------------------

// при нажатии клавиши

void __fastcall TForm2:: FormKeyPress (TObject *Sender, char &Key)

{

// если был нажат Пробел, то меняем режим вывода информации

if (Key==VK_SPACE)

info = (info+1) %3;

// если Escape, то устанавливаем переменную, которая досрочно завершит работу

// функции поиска

if (Key==VK_ESCAPE)

newprocess = true;

// при начальном режиме вывода информации

if (info==0)

if (process)

Caption="Производится поиск пути. (вкл/откл информацию - Пробел)";

else

Caption="Путь найден (для смены вида - Пробел)";

if (! info&&! process)

Caption="Текущий путь забирает монет: "+IntToStr (max)

+"; через "+IntToStr (a [A. x] [A. y]. number) +" комнат";

Draw ();

}

// если идет процесс поиска, то нельзя выходить

// ---------------------------------------------------------------------------

void __fastcall TForm2:: FormCloseQuery (TObject *Sender, bool &CanClose)

{

if (process) CanClose=false;

}

// ---------------------------------------------------------------------------

// выход из программы

void __fastcall TForm2:: FormClose (TObject *Sender, TCloseAction &Action)

{

Application->Terminate ();

}

// ---------------------------------------------------------------------------

// нажатие кнопки мыши

void __fastcall TForm2:: FormClick (TObject *Sender)

{

// если процесс поиска уже запущен, то уведовляем и уходим

if (process) {

Caption="Идет поиск. Для остановки нажмите Escape";

return; }

// заново создаем лабиринт

newprocess = false;

CreateLabirint ();

// создаем корень дерева

root = new leaf;

root->parent = NULL;

max = 0;

info = 0;

// отрисовываем пусто лабиринт

Draw ();

Caption="Производится поиск пути. (вкл/откл информацию - Пробел)";

process = true;

// ищем путь.

root->GrowTree (A,root);

// отрисовываем

Draw ();

// если так и не нвшли

if (max==0) {

Caption="Путь невозможно найти! Лабиринт следует перестроить!";

ShowMessage ("Путь невозможно найти! Лабиринт следует перестроить!");

} else {

// если нашли, то выводим сообщения

Caption = "Путь найден!";

ShowMessage ("Найден путь, проходящий через "+IntToStr (a [A. x] [A. y]. number) +" комнат");

ShowMessage ("Собрано монет: "+IntToStr (max)); }

process = false;

}

// ---------------------------------------------------------------------------

// устанавливаем размеры графического буфера

void __fastcall TForm2:: FormCreate (TObject *Sender)

{

buffer->Width=Form2->Width;

buffer->Height=Form2->Height;

Draw ();

}

// ---------------------------------------------------------------------------