Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Листинг 12.5. Поиск маршрута

unit road_;

Interface

Uses

Windows, Messages, SysUtils, Classes, Graphics, Controls,

Forms,Dialogs, StdCtrls, Grids;

Type

TForml = class (TForm)

StringGridl: TStringGrid;

Edit1: TEdit; Edit2: TEdit;

Label1: TLabel; Label2: TLabel;

Label3: TLabel; Label4: TLabel;

Button1: TButton;

procedure FormActivate(Sender: TObject);

procedure ButtonlClickfSender: TObject);

private { Private declarations }

public { Public declarations }

end;

Var

Form1: TForm1;

Implementation

{$R *.DFM}

procedure TForml.FormActivate(Sender: TObject);

var i:integer;

Begin

// нумерация строк

for i:=1 to 10 do

StringGrid1.Cells[0,i]:=IntToStr(i); // нумерация колонок

for i:=1 to 10 do

StringGrid1.Cells[1,0]:=IntToStr(i);

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

StringGridl.Cells[1,2]:='1'

StringGridl.Cells[2,l]:='1'

StringGridl.Cells[1,3]:='1'

StringGridl.Cells[3,1]:='1'

StringGridl.Cells[1,4]:='1'

StringGridl.Cells[4,1]:='1'

StringGridl.Cells[3,7]:='1'

StringGridl.Cells[7,3]:='1'

StringGridl.Cells[4,6]:='1'

StringGridl.Cells[6,4]:='1'

StringGridl.Cells[5,6]:='1'

StringGridl.Cells[6,5]:='1'

StringGridl.Cells[5,7]:='1'

StringGridl.Cells[7,5]:='1'

StringGridl.Cells[6,7]:='1'

StringGridl.Cells[7,6]:='1'

end;

procedure TForml.ButtonlClick(Sender: TObject);

Const

N=10;// кол-во вершин графа

Var

map:array[1..N,1..N]of integer;

// Карта.map[i,j]не 0, если точки i и j соединены

road:array[1..N]of integer; // Дорога - номера точек карты

incl:array[1..N]of boolean; // incl [1]равен TRUE, если точка

// с номером i включена в road

start,finish:integer; // Начальная и конечная точки

f ound:boolean; i,j:integer;

procedure step(s,f,p:integer);

Var

с:integer;// Номер точки, в которую делаем очередной шаг

i:integer;

Begin

if s=f then begin

// Точки s и f совпали!

found:=TRUE;

Labell.caption:=Labell.caption+#13+'Путь:';

for i:=l to p-1 do

Labell.caption:=Labell.caption+' '+IntToStr(road[i]);

End

Else begin

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

for c:=l to N do

begin // проверяем все вершины

if (map[s,c]<> 0) and (NOT incl(c))

// точка соединена с текущей и не включена в маршрут

Then begin

road[p]:=c;// добавим вершину в путь

incl[c]:=TRUE;// пометим вершину как включенную

step(c,f,p+l); incl[c]:=FALSE; road[p]:=0;

end;

end;

end;

end; // конец процедуры step

Begin

Label1.caption: =' ';

// инициализация массивов

for i:=1 to N do road[i]:=0;

for i:=1 to N do incl[i]:=FALSE;

// ввод описания карты из SrtingGrid.Cells

for i:=l to N do

for j:=1 to N do

if StringGrid1.Cells[i,j] <> ''

then map[i,j]:=StrToInt(StringGrid1.Cells[i, j];

else map[i,j]:=0;

start:=StrToInt(Editl.text);

finish:=StrToInt(Edit2.text);

road[l]:=start;// внесем точку в маршрут

incl[start]:=TRUE;// пометим ее как включенную

step(start,finish,2); //ищем вторую точку маршрута

// проверим, найден ли хотя бы один путь

if not found

then Labell.caption:='Указанные точки не соединены!';

end;

End.

При запуске программы в момент активизации формы приложения происходит событие onActivate, процедура обработки которого заполняет массив StringGrid1.cells значениями, представляющими описание карты. Этаже процедура нумерует строки и столбцы таблицы, заполняя зафиксированные ячейки первого столбца и первой строки StringGrid1.

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