\textit{Автор задачи и разработчик: Михаил Ермольев}
\vspace{0.2em}



Эту задачу можно решать по разному, но мы приведём одна из простейших решений. Простой проход по всем клеткам с проверкой может ли она быть покрыта.

Пусть у каждой клетки будет три состояния <<Точно нельзя покрыть>>~--- $Blocked$, <<Возможно можно покрыть>>~--- $InProgress$, <<Точно можно покрыть>>~--- $Done$. Чтобы не усложнять, давайте отдельно проверять можно ли побрить клетку вертикально или горизонтально. Разберём горизонтальную проверку, вертикальная аналогична.

Условимся, что над нашим массивом есть строка полностью заполненная $Blocked$. Давайте обрабатывать строку $j$. Будем пробегаться по строке, помечая все клетки которые нельзя брить как $Blocked$, а те которые можно брить как $InProgress$ и считать количество подряд идущих клеток в переменной $count$. Как только мы дойдём до $Blocked$ клетки или до конца строки, проверяем $k \leqslant count$.

Если это так, то пробегаемся назад на $count$ клеток и проверяем клетки строки $j - 1$ там мы считаем клетки типа $Done$ и $InProgress$ в $pred \textunderscore count$ и для всех отрезков $k \leqslant pred \textunderscore count$ ставим в линиях $j$ и $j + 1$ $Done$, иначе в линии $j - 1$ заменяем в этом отрезке $InProgress$ на $Blocked$.

В случае, когда $k > count$. Пробегаемся по строкам $j$ и $j - 1$ и заменяем все $InProgress$ на $Blocked$.

Потом делаем аналогичное по вертикали и в конце проверяем, что каждая нужная по условию клетка покрыта хотя бы в одной матрице.

Данное решение не является оптимальным, однако кажется самым простым.