Informatika gyűjtemény

Egy szinttel feljebb vidampark.dpr

2004050607080910

<<  12. óra  >>

<<  Vidámpark  >>

NézetNyomtat

vidampark.dpr (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 2 KB
program vidampark;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var n,k, esz: integer;                        { Csúszok száma, jegyek száma, élek száma }
    elek: array [1..100,1..100] of boolean;   { Ebben tárolom az éleket, az elsö indexböl a másodikba mutatnak }
    hely: integer;                            { Ez adja meg, melyik csúcsban vagyok a bejárásnál }
    utvonal: array [1..200] of integer;       { Ebben tárolom az útvonalat, amelyen jöttem }
    sorszam: integer;                         { Megadja, hogy hányadik lépésnél tartok }
    vege:boolean;                             { Ha ez igaz, akkor nem kell tovább keresni }

procedure init(); { Adatok beállítása }
var i,l: integer;
    f: text;
begin
  vege:=false;
  for i:=1 to 100 do begin
    utvonal[i]:=1;
    for l:=1 to 100 do begin
      elek[i,l]:=false;
    end;
  end;  { Adatokat kiolvasom }
  assign(f,'forras/vidam.be9');  { Más teszadatok kipróbálásához változtasd meg a forrásfile-t! (pl forras/vidam.be5, 1-9-ig vannak források) }
  reset(f);
  read(f,n);
  read(f,esz);
  readln(f,k);
  repeat
    read(f,i);
    readln(f,l);
    elek[i,l]:=true;
  until eof(f);
  close(f);
end;

procedure kesz(); { Ez történik, ha találok egy utat, ami jó }
var i: integer;   { Kiírom az eredményt }
begin
  writeln('Sikerult!');
  write('Az utvonal: ');
  for i:=1 to k do begin
    write(' '+inttostr(utvonal[i]));
  end;
end;

procedure failed(); { Ez történik, ha nincs jó útvonal. }
begin
  writeln('Nem sikerult.');
end;

procedure tovabb(h: integer);  { Ez a rekurzív függvény, mely a backtrack-et elvégzi. }
var i: integer;
begin
  if (not vege) then begin      { Csak akkor kell továbbmenni, ha még nincs egy megoldásom sem. }

  if (sorszam = k) then begin   { Fontos, hogy ne legyen k-nál több lépés összesen }
    if (hely=n) then begin      { Ha k. lépésben a kijáratnál vagyok, találtam egy jó útvonalat. }
      vege:=true;
      kesz();
    end;
  end else begin                { Ha nem, folytatom a bejárást. }
    for i:=1 to n do begin      { Megnézem, hova tudok menni onnan, ahol vagyok }
      if (elek[h,i]) then begin
        hely:=i;
        sorszam:=sorszam+1;
        utvonal[sorszam]:=hely;
        tovabb(hely);           { Ha találok egy szomszédos csúcsot, arra megyek tovább }
      end;
    end;
  end;
  if (not vege) then begin      { Ha az elsö lépésig visszaléptem és nincs több lehetséges útvonal, akkor nincs megoldás. }
    if (sorszam=1) then begin
      failed();
    end else begin              { Ha ebböl a csúcsból nincs jó útvonal, de nem az elsö lépésben vagyok, vissza kell lépnem egyet. }
      sorszam:=sorszam-1;
      hely:=utvonal[sorszam];
    end;
  end;

  end;
end;

procedure start();   { Ez a függvény indítja el a backtrack-et }
begin
  hely:=1;
  sorszam:=1;
  tovabb(1);
end;

begin
    init();
    start();
    readln;
end.
(Vissza)