\documentclass[12pt]{article}
\input{structure.tex}
\renewcommand{\bottomtitlespace}{3cm}

\begin{document}

\renewcommand{\tl}{$1$ сек.}
\renewcommand{\ml}{$256$ MB}
\problem{Задача GT21. ОБОБЩЕНИ ШАХМАТНИ ИГРИ}
\addauthor{Автор: Кинка Кирилова-Лупанова}{2026}{06}{26}
\renewcommand{\header}{
	ТРЕНИРОВЪЧНО СЪСТЕЗАНИЕ\\
	НА РАЗШИРЕНИЯ НАЦИОНАЛЕН ОТБОР\\
	София, 27 юни 2026 г.\\
	Група G
}

\begin{wrapfigure}{r}{0.35\textwidth}
	\begin{adjustbox}{width=0.35\textwidth}
		\includegraphics{chess.jpg}
	\end{adjustbox}
\end{wrapfigure}
Станимир решил да се научи да играе обобщен шах. За тази цел той  подготвил шахматна дъска с размери $n × n$. Клетката на пресечната точка на $i$-тия ред и $j$ -я стълб той оцветил в цвят $a_{i j}$. 

Станимир е начинаещ играч и може да е оцветил дъската неправилно. Затова някои клетки на дъската може да се наложи да бъдат пребоядисани в друг цвят. Дъската се счита за правилно оцветена, ако са изпълнени следните две условия:

\begin{itemize}
    \item клетките на дъската са оцветени в не повече от два различни цвята;
    \item на дъската няма две клетки с обща страна, които са оцветени в един и същи цвят.
\end{itemize}

Станимир се замислил, че играта на голяма дъска ще бъде твърде трудна за него. Поради това той може да изреже от своята дъска по-малка дъска, съдържаща първите $r$ реда и първите $c$ стълба, и да оцвети правилно само тази част.

 Напишете програма \texttt{\textbf{chess}}, която за всяка двойка числа $r$ и $c$ намира стойността $b_{r c}$  — минималния брой клетки, които Станимир трябва да пребоядиса, така че правоъгълният участък на дъската, състоящ се от първите $r$  реда и първите $c$ стълба, да бъде оцветен правилно.

\subsection{Вход}
От първия ред на стандартния вход се въвежда  едно цяло число $n$ - размер на дъската.

В следващите $n$ реда е дадено описание на дъската: $i$-тият от тези редове съдържа $n$  цели числа $a_{i 1}, \ldots, a_{i n}$  — цветовете на клетките, намиращи се в $i$-тия ред на дъската.


\subsection{Изход}
На стандартния изход програмата трябва да изведе $n$ реда,  като $i$-тият ред трябва да съдържа $n$ числа $b_{i 1}, \ldots, b_{i n}$.

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
	\item $1 \leq n \leq 400 $
	\item $1 \leq a_{i j} \le 10^9$
	\item $1 \leq  r  \leq n$
	\item $1 \leq  c  \leq n$
  \end{itemize}  

     \subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \textbf{Допълнителни ограничения} \\
		\hline
		$1$ & $23$ & $  n \leq 50$  \\ 
		\hline
		$2$ & $29$ & $ n \leq 200$  \\ 
		\hline
		$3$ & $11$ & $ a_{i j}  \leq 2$  \\ 
		\hline
		$4$ & $9$ & $ a_{i j}  \leq 10$  \\ 
		\hline
			$5$ & $9$ & $ a_{i j}  \leq 100 $  \\ 
		\hline
			$6$ & $19$ & $ - $  \\ 
		\hline
		
	\end{tblr}
	
\end{table}
  
  
\subsection{Примери}
\begin{table}[H]
	\begin{tblr}{|l|l|}
		\hline
		\textbf{Вход} & \textbf{Изход}  \\
		\hline
		\texttt{\makecell[lt]{2\\
7 7\\
7 7\\
 }}
		& 
		\texttt{\makecell[lt]{0 1\\
		    1 2\\
		}}
		
		 
\\
		\hline 
	\texttt{\makecell[lt]{3\\
1 1 2\\
2 4 4\\
3 1 2
\\ }}
		& 
		\texttt{\makecell[lt]{0 1 1\\
		    0 2 4\\
		    1 3 5\\
		}}
		
		 
\\
		\hline 		
	
	\end{tblr}
\end{table}
\FloatBarrier
	
\end{document}
