{ Dežimtoji moksleivi— informatikos olimpiada }
{ Tre‡iojo etapo antroji dalis, Jaunesni—j— grup‚ }
{ U‘davinys "Dvipartin‚ sistema" (164 u‘d.) }

{ Id‚ja.
  1. Suskai‡iuojame abiej— valstybi— plot… ir randame j— sostines.

  2. Patikriname, ar valstybi— teritorijos vientisos. Tai darome
     iž kiekvienos valstyb‚s sostin‚s rekursižkai eidami Ť visas
     keturias puses. Po to sulyginame tikr…jŤ kiekvienos valstyb‚s
     plot… su apeituoju.

  Jei teritorijos n‚ra vientisos,

  3. Imame bet kuri… sostinŠ (pavyzd‘iui, juod—j—) ir nuo sostin‚s
     iki kurio nors kražto (kražtas tai viržutin‚ ar apatin‚ eilut‚,
     kairysis ar dežinysis stulpelis) "nuvedame" juod— rajon— juost….
     Pasirenkame tokŤ kražt…, kad nei jame, nei kelyje neb–t— balt—j—
     sostin‚s. Jei juod—j— sostin‚ yra kražte ir tam kražte n‚ra balt—j—
     sostin‚s, nieko nedaroma.

          1 pavyzdys               2 pavyzdys
     ***....        ???????     ***....        *??????
     .*-....        ??*****     .*.....        *??????
     .*.....  -->   ???????     -*.....  -->   *??????
     +*..*..        .??????     +*..*..        .??????

 4. Toliau pildome ‘em‚lapŤ juod—j— rajonams skirdami po vien… stulpelŤ
    (eilutŠ), prad‚dami nuo to kražto kurŤ pasiek‚ juod—j— linija.
    Eilut‚ (stulpelis) pildoma, jei joje n‚ra balt—j— sostin‚s. Jei ten
    yra balt—j— sostin‚, pasisukama 90 laipsni— kampu ir pildoma kita
    eilut‚ (stulpelis).


          3 pavyzdys  (Pildomi dežinieji stulpeliai)
     ******.        ??????*      ?????**       ????***     ???****
     .*-.***        ??*****      ??*****       ??*****     ??*****
     .*.*.**  -->   ??????*  --> ?????**  -->  ????*** --> ???**** -->
     +**.*..        .?????*      .????**       .???***     .??****

     ??*****                          ..*****
     ??*****   U‘pildyti visi         ..*****
     ???****  -->  juod—j— rajonai    ...****
     .??****                          ...****

     Pildant ‘em‚lapŤ svarbu tinkamai pasirinkti stulpelius (eilutes),
     kuriuos pildysime. 4 pavyzdyje parodyta situacija, kai netinkamai
     pasirinkus pildom… stulpelŤ, neu‘pildyta teritorija tapo nejungi:

         4 pavyzdys
         ???????      ???????    ??????*       *******      *******
         ???.???      ???.???    ???.??*       ???.??*      *..+..*
         ?*????? -->  ?****** -->?******  -->  ?****** -->  *-*****
         ???????      ???????    ??????*       ??????*      *.....*
                                               (4 pav.)
     źiuo atveju u‘pild‘ius viržutinŠ eilutŠ (4 pav.), reik‚jo pasisukti ne
     Ť kairŠ o Ť dežinŠ. źioje situacijoje kairiojo stulpelio pildym…
     vadinsime "pavojingu". Tai darysime tik tada, jei negal‚sime pildyti
     kito stulpelio ar eilu‡i—.

  Jei atliekant tre‡i… ar ketvirt… punktus, u‘pildomi visi juod—j— rajonai,
  t— punkt— vydymas nutraukiamas ir visi likŠ rajonai paskiriami baltiesiems.

  5. Jei n = 1 ar m = 1, tuomet baigus pildym… reikia patikrinti, ar valstybi—
     teritorijos vientisos. Mat tokiu atveju gali b–ti neŤmanoma pakeisti
     ‘em‚lapio (5 pvz.) :  .....*****+-


{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+}
{$M 16384,0,655360}
program dvipartine_sistema;
  const PRAD = 'PART.DAT'; { pradini— duomen— failas }
        REZ = 'PART.REZ';  { rezultat— failas }
        MAX = 50; { 'n' ir 'm' maksimumas }
  type zemelapis = array [1..MAX, 1..MAX] of char;
       rajonas = record
                    x, y: integer; { rajono koordinat‚s }
                  end;
      linija = (kaire, virsus, desine, apacia);

  function succ_l (l: linija): linija;
  begin
    if l = apacia
       then succ_l := kaire
       else succ_l := succ (l);
  end; { kita }

  procedure dydis_sostine (zem: zemelapis; n, m: integer;
                           var balt, juod: integer;
                           var b_sost, j_sost: rajonas);
  { randa abiej— valstybi— dyd‘ius ir sostines }
    var x, y: integer;
  begin
    balt := 0; juod := 0;
    for x := 1 to n do
      for y := 1 to m do
        begin
          if zem[x, y] in ['.', '+']
             then balt := balt + 1
             else if zem[x, y] in ['*', '-']
                     then juod := juod + 1;
          if zem[x, y] = '+'
             then begin  { rasta balt—j— sostin‚ }
                    b_sost.x := x; b_sost.y := y
                  end
             else if zem[x, y] = '-'
                  then begin { rasta juod—j— sostin‚ }
                         j_sost.x := x; j_sost.y := y
                       end;
         end;
  end; { dydis_sostin‚ }

  procedure pildyti (nr, nuo, iki, pokytis: integer;
                     spalva: char;
                     eilute: boolean; { ar eilutŠ, ar stulpelŤ pildyti }
                    var liko: integer; var zem: zemelapis);
  { eilutŠ (stulpelŤ), kurios numeris "nr", tuž‡ius langelius u‘pildo }
  { duota spalva, kai ‘inoma, kad žia spalva reikia u‘pildyti "liko" }
  { langeli— }
    var kiek: integer;
  begin
    kiek := abs (nuo - iki) + 1;
    while (kiek > 0) and (liko > 0) do
      begin
        if eilute and (zem[nr, nuo] = ' ')
           then begin
                  zem[nr, nuo] := spalva;
                  liko := liko - 1;
                end
           else if not eilute and (zem[nuo, nr] = ' ')
                   then begin
                          zem[nuo, nr]:= spalva;
                          liko := liko - 1;
                        end;
        nuo := nuo + pokytis;
        kiek := kiek - 1;
      end;
  end; { pildyti }

  procedure krastas (b_sost, j_sost: rajonas; n, m: integer;
                     var juod: integer; var zem: zemelapis;
                     var l: linija);
  { padaro juod— rajon— linij… nuo sostin‚s iki to kražto, }
  { kuriame n‚ra balt—j— sostin‚s. T… kražtinŠ linij… taip pat }
  { paskiria juodiesiems }
  begin
    if (b_sost.x <> 1) and (j_sost.x <> n) and
       ((b_sost.y <> j_sost.y) or (b_sost.x > j_sost.x))
       then begin { pirma eilut‚ }
              pildyti (j_sost.y, j_sost.x, 1, -1, '*', false, juod, zem);
              pildyti (1, j_sost.y, 1, -1, '*', true, juod, zem);
              l := virsus;
            end
    else if (b_sost.x <> n) and (j_sost.x <> 1) and
            ((b_sost.y <> j_sost.y) or (b_sost.x < j_sost.x))
       then begin  { paskutin‚ eilut‚ }
               pildyti (j_sost.y, j_sost.x, n, 1, '*', false, juod, zem);
               pildyti (m, j_sost.y, m, 1, '*', true, juod, zem);
               l := apacia;
            end
    else if (b_sost.y <> 1) and (j_sost.y <> m) and
            ((b_sost.x <> j_sost.x) or (b_sost.y > j_sost.y))
       then begin  { pirmas stulpelis }
              pildyti (j_sost.x, j_sost.y, 1, -1, '*', true, juod, zem);
              pildyti (n, j_sost.x, n, 1, '*', false, juod, zem);
              l := kaire;
            end
    else if (b_sost.y <> m) and (j_sost.y <> 1) and
            ((b_sost.x <> j_sost.x) or (b_sost.y < j_sost.y))
       then begin { paskutinis stulpelis }
              pildyti (j_sost.x, j_sost.y, m, 1, '*', true, juod, zem);
              pildyti (1, j_sost.x, 1, -1, '*', false, juod, zem);
              l := desine;
            end;
  end; { kražtas }

  procedure sudaryti (n, m, { ‘em‚lapio matmenys }
                      balt, juod: integer; { abiej— valstybi— dyd‘iai }
                      b_sost, j_sost: rajonas;
                      var zem: zemelapis { pakeistasis ‘em‚lapis });
  { sudaro nauj… ‘em‚lapŤ }
    var viso, eil_v, eil_a, st_d, st_k, i, j: integer;
        pavojinga, l: linija;
        galima: boolean;
  begin
    { ‘em‚lapis ižvalomas }
    for i := 1 to n do
      for j := 1 to m do
        zem[i, j] := ' ';
    { pa‘ymimos sostin‚s }
    zem[b_sost.x, b_sost.y] := '.';
    zem[j_sost.x, j_sost.y] := '*';
    balt := balt - 1; juod := juod - 1;
    { juodiesiems padaromas iž‚jimas nuo sostin‚s iki kražto }
    { stengiantis, kad balt—j— sostin‚ neb–t— tame pa‡iame kražte }
    krastas (b_sost, j_sost, n, m, juod, zem, l);
    eil_v := 1; eil_a := n;
    st_k := 1;  st_d := m;
    pavojinga := succ_l(succ_l(l));
    while juod > 0 do
      begin
        case l of
          kaire: begin
                   galima := (b_sost.y <> st_k);
                   if galima then
                     begin
                      if zem[1, st_k] = '*'
                        then pildyti (st_k, 1, n, 1,  '*', false, juod, zem)
                        else pildyti (st_k, n, 1, -1, '*', false, juod, zem);
                      st_k := st_k + 1;
                     end
            end;
          desine: begin
                    galima := (b_sost.y <> st_d);
                    if galima then
                     begin
                       if zem[1, st_d] = '*'
                        then pildyti (st_d, 1, n, 1, '*', false, juod, zem)
                        else pildyti (st_d, n, 1, -1, '*', false, juod, zem);
                        st_d := st_d - 1;
                      end
                  end;
          virsus: begin
                    galima := (b_sost.x <> eil_v);
                    if galima then
                      begin
                        if zem[eil_v, 1] = '*'
                          then pildyti (eil_v, 1, m, 1, '*', true, juod, zem)
                          else pildyti (eil_v, m, 1, -1, '*', true, juod, zem);
                        eil_v := eil_v + 1;
                      end
                  end;
          apacia: begin
                    galima := (b_sost.x <> eil_a);
                    if galima then
                      begin
                        if zem[eil_a, 1] = '*'
                         then pildyti (eil_a, 1, m, 1, '*', true, juod, zem)
                         else pildyti (eil_a, m, 1, -1, '*', true, juod, zem);
                        eil_a := eil_a + 1;
                      end
                  end;
        end; { case }
        { apskai‡iuosime keliomis kryptimis galime eiti }
        { jei u‘pildyta iž viso viena linija, galima pildyti }
        { linijas iž abiej— jos žon—, jei u‘pildyta daugiau linij—, }
        { galima pildyti bet kuri… (jei ten n‚ra balt—j— sostin‚s ir }
        { jei ten n‚ra pavojinga }
        viso := ord(b_sost.y <> st_d) + ord(b_sost.y <> st_k) +
                ord(b_sost.x <> eil_a) + ord(b_sost.x <> eil_v);
        if (viso = 1) or (succ_l(l) <> pavojinga)
           { jei nepavojinga pildyti tolesnŠ linij… arba n‚ra pasirinkimo }
           then l := succ_l(l)
           else l := succ_l(succ_l(l));
      end;
    { u‘pildome likusius langelius }
    for i := 1 to n do
      for j := 1 to m do
        if (zem[i, j] = ' ')
            then if balt > 0
                    then zem[i, j] := '.'
                    else zem[i, j] := '*'
  end; { sudaryti }

  procedure zemel (n, m: integer;
                   var gerai, { true, jei teritorijos vientisos }
                   galima: boolean; { true, jei galima pakeisti ‘em‚l. }
                   var zem: zemelapis);

    { žis kintamasis globalus ‘emiau esan‡iai rekursinei proced–rai }
    var kopija: zemelapis;

    procedure eiti (i, j: integer; simb, spalva: char);
    { simboliu "simb" pa‘ymi visus nurodytos spalvos rajonus }
    { sujungtus su rajonu (i, j); proced–ra rekursin‚ }
    begin
      kopija[i, j] := simb;
      if (i-1 >= 1) and (kopija[i-1, j] = spalva)
         then eiti (i-1, j, simb, spalva);
      if (i+1 <= n) and (kopija[i+1, j] = spalva)
         then eiti (i+1, j, simb, spalva);
      if (j-1 >= 1) and (kopija[i, j-1] = spalva)
         then eiti (i, j-1, simb, spalva);
      if (j+1 <= m) and (kopija[i, j+1] = spalva)
         then eiti (i, j+1, simb, spalva);
    end; { eiti }

    var balt, juod, b_izol, j_izol, kiek, i: integer;
        b_sost, j_sost, xx, yy: rajonas;
  begin
    { rasime abiej— valstybi— dyd‘ius ir sostines }
    dydis_sostine (zem, n, m, balt, juod, b_sost, j_sost);
    { patikrinsime, ar valstybi— teritorijos yra vientisos }
    zem[b_sost.x, b_sost.y] := '.';
    zem[j_sost.x, j_sost.y] := '*';
    kopija := zem;
    { pa‘ymime vientisas teritorijas, sujungtas su sostin‚mis }
    eiti (b_sost.x, b_sost.y, 'b', '.');
    eiti (j_sost.x, j_sost.y, 'j', '*');
    { patikrinsime, ar yra izoliuot— teritorij— }
    dydis_sostine (kopija, n, m, b_izol, j_izol, xx, yy);
    if (b_izol = 0) and (j_izol = 0)
       then begin  { teritorijos vientisos, darbas baigiamas }
              gerai := true;
              exit
            end;
    sudaryti (n, m, balt, juod, b_sost, j_sost, zem);
    { tikinsime, ar pavyko sudaryti }
    if (n = 1) or (m = 1)
      then begin
             kopija := zem;
             { pa‘ymime vientisas teritorijas, sujungtas su sostin‚mis }
             eiti (b_sost.x, b_sost.y, 'b', '.');
             eiti (j_sost.x, j_sost.y, 'j', '*');
             { patikrinsime, ar yra izoliuot— teritorij— }
             dydis_sostine (kopija, n, m, b_izol, j_izol, xx, yy);
             galima := (j_izol = 0) and (b_izol = 0);
          end
      else galima := true;
  end; { keistis }

  { pagrindin‚ programos dalis }
  var i, j, n, m: integer;
      zem: zemelapis;
      simb: char;
      f: text;
      gerai, galima: boolean;
begin
  { duomen— skaitymas }
  assign (f, PRAD);
  reset (f);
  readln (f, n, m);
  for i := 1 to n do
   begin
     for j := 1 to m do
       read (f, zem[i, j]);
     readln (f);
   end;
  close (f);

  zemel (n, m, gerai, galima, zem);

  assign (f, REZ);
  rewrite (f);
  if gerai { valstybi— teritorijos vientisos }
     then writeln (f, 'GERAI')
     else if not galima
             then writeln (f, 'NEGALIMA')
             else for i := 1 to n do
                    begin
                      for j := 1 to m do
                        write (f, zem[i, j]);
                      writeln (f);
                     end;
  close (f);
end.