{
ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА ШУМЕНТ02 - 16 ноемв░и 2002
ТЕМА ЗА 9-10 КЛАС (ГРУПА B)

Зада╖а 2. ЛАБИРИНТ

"- Че░вени Ко▓ако - запо╖на Али▒а до▒▓а бо┐зливо - би ли ми казал кой п║▓ да
╡вана о▓▓│к?
- Зави▒и нак║де о▓ива╕ - о▓в║░на Ко▓ака.
- В▒е едно нак║де... - каза Али▒а.
- Тогава е в▒е едно кой п║▓ ╣е ╡ване╕ - ░е╖е Ко▓ака "

П░и ▒вои▓е п░икл╛╖ени┐ в С▓░ана▓а на ╖│де▒а▓а Али▒а ▒е оказала за▓во░ена в
лаби░ин▓. Понеже ▓ова било С▓░ана▓а на ╖│де▒а▓а н┐ма ни╣о ╖│дно в ▓ова, ╖е
лаби░ин▓║▓ има ┤о░ма на п░аво║г║лна м░ежа о▓ квад░а▓╖е▓а ▒ M ▒▓║лба и N ░еда.
В▒┐ко квад░а▓╖е на лаби░ин▓а е или зап║лнено - ▒▓ена - и п░ез него не може да
▒е п░еминава, или п░азно и п░ез него може да ▒е п░еминава. С║╣о ▓ака, в
лаби░ин▓а н┐ма ╢икли ▓.е. межд│ в▒еки две п░азни квад░а▓╖е▓а има един▒▓вен
п║▓. П║▓ е по▒ледова▓елно▒▓ о▓ п░азни, ▒║▒едни квад░а▓╖е▓а Ц вкл╛╖и▓елно
квад░а▓╖е▓а межд│ кои▓о е п║▓┐▓ Ц ка▓о в▒еки две квад░а▓╖е▓а о▓ п║▓┐ ▒а
░азли╖ни. Две квад░а▓╖е▓а ▒а ▒║▒едни, ако има▓ об╣а ▒▓░ана.

За да излезе о▓ лаби░ин▓а, Али▒а ▓░┐бва да из░е╖е ╖и▒ло▓о, кое▓о е д║лжина▓а
на п║▓┐ межд│ две▓е най-о▓дале╖ени п░азни квад░а▓╖е▓а▓а. Д║лжина▓а на п║▓
межд│ две квад░а▓╖е▓а е ░авна на б░о┐ на квад░а▓╖е▓а о▓ п║▓┐ мин│▒ 1.

Напи╕е▓е п░ог░ама LAB.EXE, ко┐▓о по зададен лаби░ин▓ нами░а най-гол┐ма▓а
д║лжина на п║▓ межд│ две п░азни квад░а▓╖е▓а.

В╡одни┐▓ ┤айл ▒е ╖е▓е о▓ ▒▓анда░▓ни┐ в╡од и ▒║д║░жа ╖и▒ла▓а М (3 <= М <= 1000)
и N (3 <= N <= 1000) на п║░ви┐ ▒и ░ед. В▒еки о▓ о▒▓анали▓е N ░еда ▒║д║░жа по М
▒имвола Ц в▒еки ▒имвол е или У#Ф Ц зап║лнена кле▓ка, или У.Ф Ц п░азна кле▓ка.

Из╡одни┐▓ ┤айл ▒е запи▒ва на ▒▓анда░▓ни┐ из╡од и има ▒амо един ░ед ▒ едно
╖и▒ло на него: най-гол┐ма▓а д║лжина на п║▓ межд│ две п░азни квад░а▓╖е▓а.


П░име░:

В╡од     Из╡од

7 6     8
#######
#.#.###
#.#.###
#.#.#.#
#.....#
#######

РЕШЕНИЕ:

В │▒ловие▓о на зада╖а▓а е зададен лаби░ин▓ ▒ един▒▓вен п║▓ межд│ в▒еки две
п░азни квад░а▓╖е▓а, за кой▓о ▒е ▓║░▒и ░аз▒▓о┐ние▓о межд│ две▓е м│
най-о▓дале╖ени квад░а▓╖е▓а. Това озна╖ава, ╖е можем да ░азглеждаме зада╖а▓а,
ка▓о нами░ане на ░аз▒▓о┐ние▓о межд│ два▓а най-о▓дале╖ени в║░╡а на д║░во
(▒в║░зан г░а┤ без ╢икли), к║де▓о в░║╡ на д║░во▓о е п░азно квад░а▓╖е о▓
лаби░ин▓а, а межд│ два в║░╡а имаме ░еб░о, ако ▒║о▓ве▓ни▓е им квад░а▓╖е▓а ▒а
▒║▒едни. Нека в║░╡ове▓е на д║░во▓о ▒а V на б░ой, а ░еб░а▓а Ц E.

След ка▓о ▒ме наме░или под╡од┐╣ модел за зада╖а▓а ни, да видим как можем да ┐
░е╕им. Един ди░ек▓ен под╡од е за в▒еки в░║╡ да наме░им най-о▓дале╖ени┐ о▓ него
в░║╡ ╖░ез BFS (об╡ождане в ╕и░о╖ина) или DFS (об╡ождане в д║лбо╖ина); и о▓▓ам
да наме░им два▓а най-о▓дале╖ени в║░╡а в ╢┐ло▓о д║░во. Сложно▒▓▓а на ▓ози
алго░и▓║м е V п║▓и ▒ложно▒▓▓а на BFS/DFS; BFS и DFS има ▒ложно▒▓ O(V+E), но
понеже ░азглеждаме д║░во, ▓о ░еб░а▓а ▒а O(V), ▓.е. BFS и DFS има▓ ▒ложно▒▓
O(V); ▓ака ▓ова ░е╕ение има ▒ложно▒▓ О(V^2). Понеже б░о┐▓ на в║░╡ове▓е може да
░а▒▓е по╖▓и до N*M, ▓.е. V е O(N*M) в най-ло╕и┐ ▒л│╖ай, ▓о ▓ова ░е╕ение е
незадоволи▓елно.

Една оп▓имиза╢и┐ на ▓ова ░е╕ение е да ▓║░▒им най-о▓дале╖ени┐ в░║╡ ▒амо за
в▒еки Ук░аенФ в░║╡ (в░║╡ ▒║▒ ▒▓епен 1).
                  x Ц y - . . . - z
Нека в║░╡║▓ y не е к░аен и ▒ме наме░или, ╖е най-о▓дале╖ени┐▓ в░║╡ о▓ него е z.
О▓ ▓ова, ╖е y не е к░аен (y е ▒║▒ ▒▓епен поне 2), ▓о има ▒║▒ед y, нека ▓ой е
x, кой▓о не е о▓ п║▓┐ о▓ y до z. П║▓┐▓ о▓ x до z ╣е е по-д║л║г о▓ п║▓┐ о▓ y до
z. Следова▓елно, в▒еки не-к░аен в░║╡ може да б║де п░оп│▒на▓ п░и ░е╕ение▓о
опи▒ано в п░ед╡одни┐ па░аг░а┤. Това е една много доб░а оп▓имиза╢и┐, ко┐▓о води
до много-б║░зо ░е╕ение в пове╖е▓о ▒л│╖аи и намал┐ва зна╖и▓елно кон▒▓ан▓а▓а на
▒ложно▒▓▓а на ░е╕ение▓о, но в▒е пак ░е╕ение▓о ▒и о▒▓ава ▒║▒ ▒ложно▒▓ O(V^2), в
най-ло╕и┐ ▒л│╖ай.

Да ░азгледаме д░│г под╡од к║м зада╖а▓а. П░едполагаме, ╖е знаем кои ▒а два▓а
най-о▓дале╖ени в║░╡а и нека ▓е ▒а x и y. О▓ ░аз▒║ждени┐▓а в п░еди╕ни┐ па░аг░а┤
знаме, ╖е x и y ▒а к░айни в║░╡ове. Да избе░ем п░оизволен в░║╡ w и да наме░им
най-о▓дале╖ени┐ о▓ него в░║╡ (нека ▓ой е z). Ще докажем, ╖е z е в║░╡а x или
в║░╡а y.

Нека ▒ length(i,j) озна╖им д║лжина▓а на п║▓┐ о▓ в║░╡а i до в║░╡а j. Да
░азгледаме в║зможно▒▓и▓е за w и п║▓┐ о▓ w до z ▒п░┐мо п║▓┐ о▓ x до y.
  ▒л.1) w е ╖а▒▓ о▓ п║▓┐ о▓ x до y
Да доп│▒нем ╖е z е ░азли╖ен о▓ x и y. О▓ ▓ова веднага ▒ледва, ╖е z не е о▓
п║▓┐ о▓ x до y (в п░о▓ивен ▒л│╖ай z не би бил най-о▓дале╖ени┐ о▓ w в░║╡).
            x - . . . Ц w - . . . Ц y
                        |
                        . . . Ц z
Понеже z е най-о▓дале╖ени┐ о▓ w в░║╡, ▓о length(w,z)>length(w,y). Следова▓елно
length(x,z)=length(x,w)+length(w,z)>length(x,w)+length(w,y)=length(x,y), ▓.е.
п║▓┐▓ о▓ x до z е по-д║л║г о▓ п║▓┐ о▓ x до y. П░о▓иво░е╖и ▒ избо░а на x и y.
Следова▓елно доп│▒кане▓о е нев┐░но, ▓.е. z е x или y.
  ▒л.2) w не е ╖а▒▓ о▓ п║▓┐ о▓ x до y, но п║▓┐▓ о▓ w до z п░е▒и╖а п║▓┐ о▓ x do
y; нека п░е▒и╖ане▓о ▒▓ава в║в в║░╡а u
               w - . . .
                       |
           x - . . . Ц u - . . . Ц y
                       |
                       . . . Ц z
Да доп│▒нем ╖е z е ░азли╖ен о▓ x и y. Понеже z е най-о▓дале╖ени┐ о▓ w в░║╡, ▓о
length(w,z)>length(w,y), и о▓ ▓ам length(u,z)>length(u,y). Тогава
length(x,z)=length(x,u)+length(u,z)>length(x,u)+length(u,y)=length(x,y), кое▓о
п░о▓иво░е╖и ▒ избо░а на x и y. Следова▓елно доп│▒кане▓о е нев┐░но, ▓.е. z е x
или y.
  ▒л.3) w не е ╖а▒▓ о▓ п║▓┐ о▓ x до y и п║▓┐▓ о▓ w до z не п░е▒и╖а п║▓┐ о▓ x
do y
                       z - . . . Ц w = v - . . .
                                               |
                                   x - . . . - u - . . . Ц y


      w - . . . - v - . . . - z
                  |
                  . . .
                      |
          x - . . . - u - . . . Ц y

Да озна╖им ▒ u и v два▓а най-близки в║░╡а межд│ п║▓и╣а▓а о▓ x до y и о▓ z до
w, ка▓о u е о▓ п║▓┐ о▓ x до y, а v е о▓ п║▓┐ о▓ z до w. О▓
length(w,z)>length(w,y) ▒ледва length(v,z)>length(v,y) и о▓▓ам
length(u,z)>length(u,y). Тогава
length(x,z)=length(x,u)+length(u,z)>length(x,u)+length(u,y)=length(x,y), кое▓о
п░о▓иво░е╖и ▒ избо░а на x и y. Следова▓елно доп│▒кане▓о е нев┐░но, ▓.е. z е x
или y.

В ▒║╣но▒▓, ░е╕ени┐▓а на ▒л.1 и ▒л.2 ▒а ╖а▒▓ни ▒л│╖аи на ░е╕ение▓о на ▒л.3, но
▓┐╡но▓о ░азглеждане ▒помага ▒а по-ле▒но▓о ░азби░ане на иде┐▓а, ╖е изби░айки
▒л│╖аен в░║╡ w и нами░айки най-о▓дале╖ени┐ в░║╡ за него - i, ▓о наме░ени┐▓
в░║╡ i ╣е е един о▓ два▓а най-о▓дале╖ени в║░╡а. Нами░ане▓о на в▓о░и┐
най-о▓дале╖ен в░║╡ j ▒▓ава, ка▓о наме░им най-о▓дале╖ени┐ в░║╡ за i. Така
в║░╡ове▓е i и j ▒а ▓║░▒ени▓е два в║░╡а, и д║лжина▓а на п║▓┐ межд│ ▓┐╡ е
▓║░▒ени┐ о▓гово░. Сложно▒▓▓а но ▓ова ░е╕ение е O(V) понеже п░илагаме ▒амо 2
п║▓и BFS/DFS, за да наме░им н│жни▓е най-о▓дале╖ени в║░╡ове.

Го░ни▓е ░аз▒║ждени┐ ▒а нап░авени п░и положение, ╖е имаме една двойка
мак▒имално о▓дале╖ени в║░╡ове. Ако имаме н┐колко двойки мак▒имално о▓дале╖ени
в║░╡ове, ▓о ░аз▒║ждени┐▓а ▒а ве░ни за една о▓ ▓┐╡ и пак ░е╕ава▓ зада╖а▓а.

По░ади в║зможно▒▓▓а о▓гово░║▓ на зада╖а▓а да е ▒░авни▓елно гол┐мо ╖и▒ло, ▓.е.
░аз▒▓о┐ние▓о межд│ два▓а най-о▓дале╖ени в║░╡а да е гол┐мо, използване▓о на
░ек│░▒ивно DFS не е п░епо░║╖и▓елно (има опа▒но▒▓ о▓ п░еп║лване на ▒▓ека).
По-доб░е е да ▒е ░еализи░а BFS или и▓е░а▓ивно DFS (▒║▒ ▒об▒▓вена подд░║жка на
▒▓ек). Мое▓о ░е╕ение използва BFS, ка▓о използвам ма▒ив за подд░║жка▓а на
опа╕ка Ц ▓ака задел┐м пове╖е паме▓, но не г│б┐ изли╕но в░еме в опе░а╢ии ▒
│каза▓ели.

Kristiyan Haralambiev
}

program Labirynth;
const
        InFile                  = ''; // when the name of a file is ''
        OutFile                 = ''; // the standard i/o is used
        Max                     = 1001;
        MazeSize                = Max*Max;
        Infinity                = 10234567890;
        AddI : array[1..4] of Integer = (1, 0, -1, 0);
        AddJ : array[1..4] of Integer = (0, 1, 0, -1);
var
        Maze                    : array[0..Max,0..Max] of Char;
        UnVis                   : array[0..Max,0..Max] of Boolean;
        BfsArr                  : array[1..MazeSize] of
                                        record I, J, Leng : LongInt; end;
        Ans, N, M               : LongInt;

{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure InPut;
var
        F                       : Text;
        I, J                    : LongInt;
begin
  Assign(F, InFile); ReSet(F);

  FillChar(Maze, SizeOf(Maze), '#');

  ReadLn(F, M, N);
  for I := 1 to N do begin
    for J := 1 to M do Read(F, Maze[I,J]);
    ReadLn(F);
  end;

  Close(F);
end;

{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure Solve;
var
        Ibest, Jbest, Best      : LongInt;
        BfsBeg, BfsEnd          : LongInt;

    {------------------}
    procedure Find(StartI, StartJ : LongInt);
    var
        I, J, Leng, K           : LongInt;
    begin
      //initialize queue
      BfsBeg := 1;
      BfsEnd := 2;
      BfsArr[1].I := StartI;
      BfsArr[1].J := StartJ;
      BfsArr[1].Leng := 0;
      UnVis[StartI, StartJ] := False;

      repeat
       //get queue
        I := BfsArr[BfsBeg].I;
        J := BfsArr[BfsBeg].J;
        Leng := BfsArr[BfsBeg].Leng;
        Inc(BfsBeg);

        for K := 1 to 4 do
          if (Maze[I+AddI[K],J+AddJ[K]] = '.') and (UnVis[I+AddI[K],J+AddJ[K]])
            then begin //add queue
              UnVis[I+AddI[K],J+AddJ[K]] := False;
              BfsArr[BfsEnd].I := I + AddI[K];
              BfsArr[BfsEnd].J := J + AddJ[K];
              BfsArr[BfsEnd].Leng := Leng + 1;
              Inc(BfsEnd);
            end;
      until BfsBeg = BfsEnd;

      //return values
      Best := Leng;
      Ibest := I;
      Jbest := J;
    end;
    {------------------}
var
        I, J                    : LongInt;
begin
  for I := 1 to N do
    for J := 1 to M do
      if Maze[I,J] = '.' then begin
        FillChar(UnVis, SizeOf(UnVis), True);
        Find(I,J);

        FillChar(UnVis, SizeOf(UnVis), True);
        Find(Ibest,Jbest);

        Ans := Best;
        Exit;
      end;

  Ans := 0;
end;


{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure OutPut;
var
        F                       : Text;
begin
  Assign(F, OutFile); ReWrite(F);
  WriteLn(F, Ans);
  Close(F);
end;

{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
begin
  InPut;
  Solve;
  OutPut;
end.