Roma_0297

Untitled

Feb 7th, 2012
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Delphi 1.60 KB | None | 0 0
  1. program Project2;
  2.  
  3. {$APPTYPE CONSOLE}
  4.  
  5. uses
  6.   SysUtils;
  7. var
  8.   arr : array[1..100,1..100]of byte;
  9.   used : array [1..100] of boolean;
  10.   q : array [1..100] of integer;
  11.   otvet : array[1..100] of integer;
  12.   p: array [1..100]of integer;
  13.   p1: array [1..100]of integer;
  14.   i, l, r, n, s, f, j, sum, summa : integer;
  15.   procedure BFS(n, s, f : integer);
  16.     begin
  17.       l:=1;
  18.       r:=1;
  19.       q[r]:=s;
  20.       otvet[s] := 0;
  21.       used[s]:=true;
  22.       while l <= r do
  23.         begin
  24.           for i := 1 to n do
  25.             begin
  26.               if (arr[s,i]=1) and (not used[i]) then
  27.                 begin
  28.                   inc(r);
  29.                   q[r] := i;
  30.                   used[i] := TRUE;
  31.                   otvet[i] := otvet[s]+1;
  32.                   p[i]:=s;
  33.                 end;
  34.             end;
  35.           inc(l);
  36.           s := q[l];
  37.         end;
  38.     end;
  39. begin
  40.   reset(input,'path.in');
  41.   rewrite(output,'path.out');
  42.   read(n);
  43.   summa:=0;
  44.   for i := 1 to n do
  45.     begin
  46.       for j := 1 to n do
  47.         begin
  48.           read(arr[i,j]);
  49.         end;
  50.     end;
  51.   read(s,f);
  52.   if s=f then
  53.     begin
  54.       writeln(1);
  55.       write(s);
  56.     end;
  57.   for i:=1 to n do
  58.     begin
  59.       used[i]:=false;
  60.     end;
  61.   BFS(n,s,f);
  62.   if used[f]= false then
  63.     begin
  64.       write(-1);
  65.       exit;
  66.     end;
  67.       writeln(otvet[f]);
  68.       p1[1]:=f;
  69.       sum:=f;
  70.       for i:=1 to otvet[f] do
  71.         begin
  72.           p1[i+1]:=p[sum];
  73.           sum:=p[sum];
  74.         end;
  75.       for i:=otvet[f]+1 downto 1 do
  76.         begin
  77.           write(p1[i],' ');
  78.         end;
  79.   readln;
  80.   readln;
  81. end.
Advertisement
Add Comment
Please, Sign In to add comment