{*
 * @(#) mazeprg2.pas - Program for solving 'maze' problem
 * (finding out one way in the graph from one point to another point),
 * the second version.
 * (c) 1994 Ivan Maidanski <ivmai@chat.ru> http://ivmai.chat.ru
 * Freeware program source. All rights reserved.
 **
 * Language: Turbo Pascal
 * Tested with: Turbo Pascal v7.0
 * Last modified: 1994-10-26 19:35:00 GMT+04:00
 *}

program MazeProg2;

const MaxN= 20;
type TNode= 0..MaxN;
type TMaze= array[1..MaxN,1..MaxN] of Boolean;
type TWay= array[1..MaxN] of TNode;
var N: TNode;
var Target: TNode;
var WayEnd: TNode;
var Maze: TMaze;
var Way: TWay;
function TestInput(Cond: Boolean): Boolean;
 begin
   Cond:=(IOResult=0) and Cond;
   if not Cond
     then WriteLn(' Incorrect data!');
   TestInput:=Cond
 end;
procedure EnterMaze;
 var I,J: TNode;
 var Ch: Char;
 begin
   for I:=1 to N
     do Maze[I,I]:=False;
   for I:=1 to Pred(N)
     do for J:=Succ(I) to N
          do repeat
               Write('Is there a connection between node ',I,' and ',J,
                     ': (Yes/No) ? ');
               ReadLn(Ch);
               Ch:=UpCase(Ch);
               Maze[I,J]:=Ch='Y';
               Maze[J,I]:=Maze[I,J]
             until TestInput((Ch='Y') or (Ch='N'))
 end;
procedure Init;
 begin
   repeat
     Write('Enter amount of nodes: [1..',MaxN,'] ');
     ReadLn(N)
   until TestInput((N>=1) and (N<=MaxN));
   repeat
     Write('Enter target node: [1..',N,'] ');
     ReadLn(Target)
   until TestInput((Target>=1) and (Target<=N));
   EnterMaze
 end;
procedure Run;
 var Next: TNode;
 function TestEnd: Boolean;
  begin
    TestEnd:=False;
    if WayEnd>0
      then TestEnd:=Way[WayEnd]<>Target
  end;
 function TestWay: Boolean;
  var Test: TNode;
  begin
    TestWay:=True;
    if Maze[Way[WayEnd],Next]
      then begin
             Test:=1;
             while (Way[Test]<>Next) and (Test<WayEnd)
               do Test:=Succ(Test);
             TestWay:=Way[Test]=Next
           end
  end;
 function WayNotFound: Boolean;
  begin
    WayNotFound:=False;
    if WayEnd>0
      then begin
             while (Next<N) and TestWay
               do Next:=Succ(Next);
               WayNotFound:=TestWay
             end
  end;
 procedure BackWay;
  begin
    repeat
      Next:=Way[WayEnd];
      WayEnd:=Pred(WayEnd)
    until (WayEnd=0) or (Next<N);
    if Next<N
      then Next:=Succ(Next)
  end;
 begin
   WayEnd:=1;
   Way[WayEnd]:=1;
   while TestEnd
     do begin
          Next:=1;
          while WayNotFound
            do BackWay;
          if WayEnd>0
            then begin
                   Inc(WayEnd);
                   Way[WayEnd]:=Next
                 end
        end
 end;
procedure Done;
 var Cur: TNode;
 begin
   if WayEnd=0
     then WriteLn('Cannot access the target!')
     else begin
            Write('Simple way:');
            for Cur:=1 to WayEnd
              do Write(' ',Way[Cur])
          end;
   WriteLn
 end;
begin
  Init;
  Run;
  Done
end.