\begin{tutorial}{Eight-Connected Figures}

{
    \parindent=1cm
    \begin{tabular}{l@{\extracolsep{1cm}}l}
         Идея: & Захар Яковлев\\
         Разработка: & Захар Яковлев\\
     \end{tabular}
}

Отметим, что максимальные ограничения в задаче $t = 50$, $n = 300$, а ограничение на количество запросов $30\,000$, то есть ровно $2nt$. 

Первая идея, которая приходит в голову~--- поддерживать связную область одного цвета, но тогда только среднее число запросов будет $2nt$, а разброс значений приведет к превышению числа запросов.

Правильное решение~--- поддерживать одновременно связные области белого и черного цвета. При этом нужно делать запросы в клетки, соседние с обеими областями. Тогда область нужного размера получится меньше, чем за $2n$ запросов.

Отдельно надо аккуратно обработать специальные случаи: одна область может оказаться полностью окруженной другой. В этом случае необходимо <<выкинуть>> внутреннюю область и начать строить заново область такого цвета снаружи. За счет множественных тестов неудача в одном тесте компенсируется запасом в других. Так, вероятность ошибки в авторском решении меньше $10^{-40}$.

Также бывают особые случаи, когда у каждой из областей есть соседи, но нет общих соседей:

\t{.......}

\t{.WWWWW.}

\t{.WBBBW.}

\t{.WB.BW.}

\t{.WBBBW.}

\t{.WWWWW.}

\t{.......}

Но такие случаи крайне маловероятны и на практике практически не встречаются. Также можно менять стартовую точку для обхода таких случаев.

\end{tutorial}
