Автор задачи и разработчик: Александр Гордеев
Согласно условию, каждую клетку мы можем красить сколько угодно раз. Нам важно чтобы все клетки, которые должны остаться белыми, остались белыми (красить их нельзя), а все клетки, которые должны стать красными, стали красными (необходимо чтобы хоть одна кисть задела эту клетку).
Заведем массив $$$\mathtt{state}_{i,j}$$$, который хранит состояние каждой клетки. Если $$$\mathtt{state}_{i,j} = 0$$$, то клетку $$$(i,j)$$$ нужно покрасить, если $$$\mathtt{state}_{i,j} = 1$$$, то её красить нельзя, если $$$\mathtt{state}_{i,j} = 2$$$, то её мы уже покрасили.
Теперь можно просто пройтись по матрице и попытаться поставить все возможные варианты поставить любую кисть в каждое возможное место. Если все $$$\mathtt{state}_{x,y}$$$, где $$$(x, y)$$$ — клетка, до которой мы достаём нашей текущей кистью, равны $$$0$$$ или $$$2$$$, то при таком расположении кисти нет клеток, которые красить запрещено, и мы можем поставить кисть, то есть для всех затронутых клеток присвоить $$$\mathtt{state}_{x,y} = 2$$$.
После прохода по матрице достаточно проверить, что не осталось не одной клетки, для которой $$$\mathtt{state}_{i,j} = 0$$$. Действительно, если осталась непокрашенная клетка, то ни одно расположение кисти, красящее её, не было корректным. Таким образом, если не осталось клеток со $$$\mathtt{state}_{i,j} = 0$$$, то ответ «YES», иначе «NO». Время работы решения — $$$\mathcal{O}(nm)$$$.