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