%LuaLaTeX
\documentclass[12pt]{article}
\usepackage{geometry}
\geometry{
	paper=a4paper,
	top=4cm, % Top margin
	bottom=2cm, % Bottom margin
	left=2cm, % Left margin
	right=2cm, % Right margin
	%headheight=3cm, % Header height
	%footskip=1.5cm, % Space from the bottom margin to the baseline of the footer
	%headsep=0.5cm, % Space from the top margin to the baseline of the header
	%showframe, % Uncomment to show how the type block is set on the page
}
\usepackage[T2A]{fontenc}
\usepackage[bulgarian]{babel}
\usepackage{fontspec}
\setmainfont{Times New Roman}
\setsansfont{Times New Roman}
\setmonofont{Courier New}
\usepackage[math-style=TeX]{unicode-math}
\setmathfont{Latin Modern Math}



\begin{document}

%\newcommand{\tl}{$0.1$ сек.}
%\newcommand{\ml}{$256$ MB}
{\bf Задача ДОСТИЖИМОСТ}

\bigskip


%\begin{wrapfigure}{r}{0.25\textwidth}
%	\begin{adjustbox}{width=0.25\textwidth}
%		\includegraphics{image}
%	\end{adjustbox}
%\end{wrapfigure}

{\bf Пояснение към решенията}

\bigskip

{\bf Решението за 54 т.} -- файл {\tt reach\_54p.cpp}
\bigskip

Данните от таблицата се прочитат е масива {\tt int a[M][N]}.
В проходимите клетки се записва числото {\tt DOT=-1}, а в непроходимите -- числото {\tt AST=-2}.
 Допълнително таблицата се огражда с контур, състоящ се от ред 0, ред $m+1$,
 колона $0$ и колона $n+1$, в които се записва {\tt AST=-2}, за да се избегне проверката
 за излизане извън таблицата.
 
 Прилага се вариант на алгоритъм за търсене в ширина, известен като ``Вълна''. За целта във функцията
  {\tt int wave(int is, int js)} първо се маркира стартовата клетка с 0 и след това в 
 цикъла {\tt while(b)} многократно се обхождат всички клетки на таблицата. При всяко
 обхождане в клетките се записва поредната стойност на {\tt d}, което дава отдалечеността
 (нивото) на клетката от стартовата. За целта от всяка клетка от текущото ниво
 се търсят кои клетки са нейни съседи и в тях се записва {\tt d+1}. Така {\tt d} за клетката
 показва с колко най-малко стъпки може да се достигне тази клетка. Процесът 
 продължава, докато е възможно намиране на съседи. При прекратяването на процеса, стойността 
 на {\tt d} показва на колко стъпки е най-отдалечената клетка от стартовата.
 
 За всяка поредна двойка координати $(i,j)$, за които трябва да се пресметнат стъпките до 
 най-отдалечената достижима клетка се извиква  {\tt int d=wave(i,j)}, което пресмята
 това. Поредната пресметна стойност се извежда в изхода на програмата. След всяко 
 използване на функцията {\tt wave} се извиква функцията {\tt clear()}, която възстановява
 началното състояние на масива {\tt a[][]}.  
 
 \bigskip
 
 {\bf Решението за 100 т.} -- файл {\tt reach\_100p.cpp}
\bigskip

Функциятa {\tt int wave(int is,int js)} от предишната програма тук заменяме с по-бързо работеща функция 
{\tt int bfs(int i,int j)} за търсене в дълбочина. Използва се опашка {\tt queue<pair<int,int>>q} 
от {\tt STL}. В тази опашка първоначално се вкарва двойката координати на стартовата клетка. 
След това в цикъла {\tt while(!q.empty())} се изкарва по една двойка координати 
{\tt auto p = q.front(); q.pop(); i=p.first; j=p.second;} на клетка и
за тази клетка се търсят всички нейни съседи с координати {\tt i0}, {\tt j0}, които не са били посетени.  
За тези клетки се записва ниво с единица по-голямо от предишното и след това тези клетки
се вкарват в опашката. В променливата {\tt d} се подържа най-голямото намерено ниво, което
след завършване на цикъла се подава като стойност на функцията {\tt bfs}.

\bigskip

{\bf Алтернативно решението за 100 т.} -- файл {\tt reach\_alt\_100p.cpp}
\bigskip

Задачата може да се реши без използване на опашка, а като модифицираме функцията 
{\tt wave} от {\tt reach\_54p.cpp}. Няма да правим обхождане на всички клетки $(i,j)$
от таблицата чрез двоен цикъл за всички индекси $(i,j)$, а ще използваме само тези индекси,
които са на клетките от предишното ниво.   За целта използваме два вектора {\tt pi} и {\tt pj}
за записване на индексите от предишното ниво и още два вектора {\tt pni} и {\tt pnj}, в които 
ще записваме новите индекси на клетките от текущото ниво. В края на обработката на нивото 
записваме индексите от {\tt pni} и {\tt pnj} съответно в {\tt pi} и {\tt pj}.


\bigskip

\hfill{\it Емил Келеведжиев}






	
\end{document}