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