Поиск маршрута
Листинг 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;
Button1: TButton;
Label4: TLabel;
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
StringGridl.Cells[0,i]:=IntToStr(i);
// нумерация колонок
for i:=l to 10 do
StringGridl.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]ne 0,
// если точки i и j соединены
road:array[1..N]of integer;
// Дорога - номера точек карты
incl:array[1..N]of boolean; // incl[1]равен TRUE, если точка
// с номером i включена в road
start,finish:integer; // Начальная и конечная точки
found: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 incite1)
// точка соединена с текущей и не включена в маршрут
then begin
road[p]:=c;// добавим вершину в путь
incl[c]:=TRUE;// пометим вершину как включенную
step(c,f,p+l);
incite]:=FALSE; road[p]:=0;
end;
end;
end;
end;// конец процедуры step
begin
Label1.caption: =' ' ;
// инициализация массивов
for i:=l to N do road[i]:=0;
for i:=l 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(StringGridl.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, процедура обработки которого заполняет массив StringGridl.cells значениями, представляющими описание карты. Этаже процедура нумерует строки и столбцы таблицы, заполняя зафиксированные ячейки первого столбца и первой строки StringGridl.
Поиск маршрута инициирует процедура TFormi.Buttoniciick, которая запускается щелчком на кнопке Поиск. Данная процедура для поиска точки, соединенной с исходной точкой, вызывает процедуру step, которая после выбора первой точки, соединенной с начальной, и включения ее в маршрут вызывает сама себя. При этом в качестве начальной точки задается уже не исходная, а текущая, только что включенная в маршрут.
