%LuaLaTex
\documentclass[12pt]{article}
\input{structure.tex}
\fancyhead[R]{
	\begin{minipage}{\textwidth}
		\raggedleft
		\includegraphics[width=2cm]{./logo2.png}
	\end{minipage}
}
\renewcommand{\bottomtitlespace}{2cm}

\begin{document}

\renewcommand{\tl}{$0.2$ сек.}
\renewcommand{\ml}{$256$ MB}
\problem{Задача OJ06. ДОСТИЖИМОСТ}
\addauthor{Автор: Емил Келеведжиев}{2026}{08}{29}
\renewcommand{\header}{
	НАЦИОНАЛНА ШКОЛА ПО ИНФОРМАТИКА\\
	ОТБОРНО СЪСТЕЗАНИЕ\\
	Габрово, 29 август 2026 г.\\
	6 – 7 клас
}

Дадена е правоъгълна таблица, съставена от еднакви квадратни клетки, разположени в $m$ реда и $n$ колони. Номерата на редовете и колоните започват от $1$. Клетките са два вида: проходими и непроходими. Тръгвайки от проходима клетка с координати $(i,j)$, може да отидем с една стъпка в съседна проходима клетка, разположена отгоре, отдолу, отляво или отдясно. Интересуваме се за всяка клетка, до която може да отидем, колко е най-малкият брой стъпки, с които може да направим това. 

Напишете програма \textbf{\texttt{reach}}, която от всички така описани бройки, пресмята най-голямата. Вашата програма трябва да пресметне това последователно за дадени $k$ на брой клетки, от които тръгваме.

\subsection{Вход}
На първия ред на стандартния вход са записани стойностите на $m$ и $n$, отделени с интервал. Следват $m$ реда във входа, всеки съдържащ $n$ знака, записани без разделящи ги интервали. Знаците задават проходимите и непроходимите клетки в дадената таблица, като знакът точка (\texttt{.}) означава проходима клетка, а знакът звездичка (\texttt{*}) -- непроходима. 

Следва ред във входа съдържащ стойността на $k$ и след него следват $k$ реда, всеки съдържащ две цели числа -- координатите $(i,j)$ на клетките, от които тръгваме.

\subsection{Изход}
Вашата програма трябва да изведе на един ред в изхода $k$ цели числа, равни на съответния максимален брой стъпки, последователно за клетките,от които тръгваме. Числата в изхода трябва да са отделени помежду си с точно един интервал. Когато клетката, от която тръгваме, е непроходима, за нея трябва да изведете числото $-1$.

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
    \item $1 < m < 500, 1 < n < 500, 1\le k < 50$
    \item $1\le i \le m$ и $1\le j \le n$ за координатите $(i,j)$ на клетките, от които тръгваме.
    \item В около $54\%$ от тестовете: $m$ и $n$ са по-малки от $250$.
\end{itemize}

\vspace{-2pt}
\subsection{Пример}
\begin{table}[H]
	\begin{tblr}{|l|l|X[j]|}
		\hline
		\textbf{Вход} & \textbf{Изход} & \textbf{Пояснение} \\
		\hline
		\texttt{\makecell[lt]
		{
3 7\\
*..**..\\
*..*.*.\\
...**.*\\
3\\
3 2\\
1 5\\
3 6\\
		}}
		& 
		\texttt{\makecell[lt]
		{
3 -1 0\\
		}}
		& 
		{
При тръгване от $(3,2)$ е показан минималният брой стъпки, с които може да отидем до
достижимите клетки:\\
{\tt
*23**..\\
*12*.*.\\
101**.*\\
}
Най-големият брой е $3$.\\
При тръгване от $(1,5)$ клетката е непроходима.\\
При тръгване от $(3,6)$ не е възможно да отидем в други клетки.}
		\\
		\hline
		
	\end{tblr}
\end{table}
	
\end{document}