Реализовать программу, осуществляющую поиск выхода из лабиринта методом поиска с возвратом. - C++ - Ответ 441767

const max_graf = 100;(максимальное число комнат в лабиринте}
type list =^elem;
         elem = record
                            num : integer;
                            next : list;
                      end;
var
Graf: array [1. . rnax_graf] of elem;
ref: list;
       n, i, a : integer;
       goal, go_on : boolean; {признаки достижения цели и необходимости продолжения}
      beg_num,end_num : integer;
      beg_st, end_st, elem_st : list; { начало, конец и элемент стека }
. . .
Procedure CreateGraf(n:integer);
{чтение исходных данных из текстового файла и формирование графа}
var
        sosed, sosed1 : list;
begin
        for i:=l to n do
          begin
                     new(sosed);
                     graf[i].next := sosed;
                    repeat
                              Readln(inf,a) ;
                              sosed^.num := a;
                              if а<>0 then
                              begin
                                         new(sosed1);
                                         sosed^.next := sosed1;
                                         sosed := sosed1
                              end
                    until a=0
          end
end;
 
  Формирование маршрута ведется с использованием стека. Процедуры Add и Del предназначены соответственно для добавления и удаления элементов стека.
 
Procedure Add (num: integer; var beg_st : list );
{ добавление элемента к стеку }
var
          elem_st : list;
begin
          new(elem_st); { выделили память под следующий элемент стека}
          elem_st^.next:=beg_st; {присоединили новый элемент к стеку }
                 elem_st^.num:=num; {занесли информацию)
                 beg_st:=elem_st {установили указатель на новое начало стека}
end;
 
Procedure Del (var begin_st : list ) ;
{ удалить элемент из стека }
var
        elem_st : list;
begin
        elem_st:=beg_st;
        beg_st:=beg_st^.next; { переносим указатель начала (вершины) стека на второй элемент}
        Dispose(elem_st) { освобождаем память, уничтожив первый элемент}
end;
 
  Основное действие алгоритма — это обработка очередной вершины графа, в результате чего мы либо добавляем к маршруту новую вершину, либо возвращаемся в предыдущую. Порядок просмотра соседей определяется порядком следования полей-ссылок в перечне вершин-соседей, который соответствует одной записи в текстовом файле.
 
Procedure Way (num_begin, num_end : integer); { номера вершин начала и конца пути }
var
      num : integer; { номер текущей вершины }
      flag : boolean; { признак необходимости продолжения пути }
begin
      Graf [num_begin] .num : = 1; { начальный этап }
      Add (num_begin, beg_st) ; {поместили начало пути в. стек }
      flag := true; {нужно продолжать построение пути }
      while flag and (not goal) do { строим очередной фронт }
      begin
             num := beg_st^.num ;
             { берем значение вершины стека }
             ref := graf [num].next;
          go_on := false; {признак того, что путь увеличился}
             repeat
                     a: =ref^ .num;
                     if а<>0 then
                             begin
                                        {обработка очередного соседа}
                                        if Graf[a]. num=0 {пометить вершину следующим фронтом}
                                        then begin
                                                      Graf [a].num := 1;
                                                      Add(a, beg_st) ;
                                                    go_on := true; {путь увеличился на шаг}
                                        end
 
                               else
                                       ref := ref^.next { переходим к следующему соседу }
                             end;
            until (a=0) or (go_on);
                 if Graf [num_end].num<>0 then goal :=true { дошли до цели. }
                  else
                    if not go_on then
                        begin
                             del (beg_st) ;
                             if beg_st=end_st then flag:=false
                                { стек пуст, задача неразрешима }
                        end
      end
end;
 
  Теперь программу поиска маршрута можно записать так (структура графа считывается из текстового файла):
 
program BackTracking;
. . .
begin
        for i:=1 to Max_Graf do Graf [i].num :=0;
        assign (inf, 'graf.txt');
        { в файле приведен пример, разобранный в тексте (рис.3)}
        reset (inf);
        readln (inf,n); { число вершин графа }
        CreateGraf (n) ;
        close (inf) ;
        new (elem_st) ; { инициализация стека }
        beg_st:=elem_st; { стек пока пуст,}
        end_st:=elem_st; { призак этого: beg_st = end_st}
        goal := false;
        Writeln;
        Writeln('Введите номер начальной и конечной вершины'};
        Readln (beg_num, end_num) ;
        Way (beg_num, end_num) ;
        if goal then
            { построение и печать маршрута }
      . . .
end.