{
ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА ШУМЕН’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.