pascal/BOI_ELE.PAS at master · mantask/pascal · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
{MK 2001}
{Sprendimas Baltic Olimpiad of Informatic 2000 uzdaviniui Elektronine Plokstele}
program BOI_PLOKSTELE;
  Type Tats = record {rasto mazgo grandines kelias}
              num : word;
              kryptys : string
      end;
      Ttinkl = array [1 .. 15, 1 .. 15] of 0 .. 2;
  var ck, ckx, cky, {pagalbiniai ciklo kintamieji}
      pg, {kiek ziedu sudaro el plokstele, reikalingas ciklui}
      kr,{reikalingas ziedam tikrinant}
      ilg : byte;{tinklelio iligis}
      tinkl : Ttinkl;{tinklelis. 0-tuscia,1-mazgas,2-grandine}
      max : word;{max rastu kontaktu skaicius}
      f : text;{tekstinis failas}
      pgAts, Atsak : string; {pagalbinis kvieciant galima procedura}
      pgTaip : boolean; {ar galima sujungti}
      ats : Tats;{mazgo numeris ir jungimo kelias}
      mATS : array [1 .. 120] of Tats;{galutinis atsakymas su mazgu nr ir keliais}

{varant visa sita suda reikai tikrinti ar rastas rekursiskas kelias yra trumpiausias}
{reikia sutvarkyti, kad 2 irasytu i tinlk tik paciam gale, kai jau rastas trumpiausias kelias ir isnagrineti visis variantai}
  procedure galima (x, y : byte; var tinkl : Ttinkl; var taip : boolean; var pgats : string; ats : string);
  begin
    if taip then
    begin
      if (pgAts = '') or (length (ats) < length (pgAts)) then pgAts := ats;
      exit
    end
    else begin
{E}   if (x + 1) > ilg then begin taip := true; exit end
      else if not taip and (tinkl [x + 1, y] = 0) then
      begin
        if tinkl [x, y] <> 1 then tinkl [x, y] := 2;
        galima (x + 1, y, tinkl, taip, pgAts, ats + 'E');
        if not taip then tinkl [x, y] := 0;
      end;
{W}   if (x - 1) < 1 then begin taip := true; exit end
      else if not taip and (tinkl [x - 1, y] = 0) then
      begin
        if tinkl [x, y] <> 1 then tinkl [x, y] := 2;
        ats := ats + 'W';
        galima (x - 1, y, tinkl, taip, pgAts, ats);
        if not taip then ats := copy (ats, 1, length (ats) - 1);
        if not taip then tinkl [x, y] := 0;
      end;
{N}   if (y - 1) < 1 then begin taip := true; exit end
      else if (not taip and (tinkl [x, y - 1] = 0)) then
      begin
        if tinkl [x, y] <> 1 then tinkl [x, y] := 2;
        ats := ats + 'N';
        galima (x, y, tinkl, taip, pgAts, ats);
        if not taip then ats := copy (ats, 1, length (ats) - 1);
        if not taip then tinkl [x, y] := 0;
      end;
{S}   if (y + 1) > ilg then begin taip := true; exit end
      else if not taip and (tinkl [x, y + 1] = 0) then
      begin
        if tinkl [x, y] <> 1 then tinkl [x, y] := 2;
        ats := ats + 'S';
        galima (x, y, tinkl, taip, pgAts, ats);
        if not taip then ats := copy (ats, 1, length (ats) - 1);
        if not taip then tinkl [x, y] := 0;
      end
    end
  end;

begin
  {nuskaitomi prad. duomenys}
  assign (f, 'ele.in');
  reset (f);
  readln (f, ilg);
  for cky := 1 to ilg do
  begin
    for ckx := 1 to ilg do
    read (f, tinkl [ckx, cky]);
    readln (f);
  end;
  close (f);

  {tikrinami visi mazgai}
  max := 0; {kol kas nera rastu susungtu mazgu}
  if ilg mod 2 = 1 then pg := ilg div 2 + 1
                   else pg := ilg div 2;
  kr := 0;
  while kr < pg do
  begin
    for ckx := 1 + kr to ilg - kr do
    begin
      if tinkl [ckx, kr + 1] = 1 then
      begin
        pgTaip := false;
        pgAts := '';
        galima (ckx, 1 + kr, tinkl, pgTaip, pgAts, atsak);
        if pgTaip then
        begin
          inc (max);
          mAts [max].num := ckx;
          mAts [max].kryptys := pgAts;
        end;
      end;
      if tinkl [ckx, ilg - kr] = 1 then
      begin
        pgTaip := false;
        pgAts := '';
        galima (ckx, ilg - kr, tinkl, pgTaip, pgAts, atsak);
        if pgTaip then
        begin
          inc (max);
          mAts [max].num := ilg * (ilg - 1) + ckx;
          mAts [max].kryptys := pgAts;
        end;
      end;
    end;
    for cky := 1 + kr to ilg - kr do
    begin
      if tinkl [kr + 1, cky] = 1 then
      begin
        pgTaip := false;
        pgAts := '';
        galima (kr + 1, cky, tinkl, pgTaip, pgAts, atsak);
        if pgTaip then
        begin
          inc (max);
          mAts [max].num := ilg * (cky - 1) + 1;
          mAts [max].kryptys := pgAts;
        end;
      end;
      if tinkl [ilg - kr, cky] = 1 then
      begin
        pgTaip := false;
        pgAts := '';
        galima (ilg - kr, cky, tinkl, pgTaip, pgAts, atsak);
        if pgTaip then
        begin
          inc (max);
          mAts [max].num := ilg * cky;
          mAts [max].kryptys := pgAts;
        end;
      end;
    end;
    inc (kr)
  end;

  {surasomi atsakymai}
{  assign (f, 'ele.out');
  rewrite (f);
}  writeln ({f,} max);
  for ck := 1 to max do
  begin
    write ({f, }mATS [ck].num, ' ');
    pg := 1;
    while mATS [ck].kryptys [pg] <> '' do
    begin
      write ({f,} mATS [ck].kryptys [pg]);
      inc (pg);
    end;
  end;
{ close (f);}
end.