Задачу можно решить методом динамического программирования по изломанному профилю. Состоянием является разбиение черных клеток, находящихся в текущем профиле, на компоненты связности. При переходе нужно выбрать цвет текущей клетки из двух вариантов: белого и черного. Стоимость перехода равна $$$0$$$, если клетка уже имеет такой цвет, и $$$1$$$, если исходно цвет клетки противоположный. Состояние можно задавать массивом целых чисел длины $$$m$$$, в котором $$$i$$$-е число равно $$$-1$$$, если соответствующая клетка покрашена в белый цвет, и какому-то неотрицательному числу иначе. Причем, если две черные клетки находятся в одной компоненте связности, им соответствуют одинаковые числа, а иначе — разные.
При переходе, в котором текущая клетка красится в белый, нужно проверять, что каждая компонента связности все еще имеет представителя в следующем изломанном профиле. Это может нарушиться только если соседняя сверху клетка — черная, и является единственным представителем своей компоненты связности. При переходе, в котором текущая клетка красится в черный, нужно проверять, что не образовался цикл по черным клеткам. Это может произойти только в том случае, если соседние клетки слева и сверху являются черными и лежат в одной компоненте связности.
Если переход корректен, нужно построить новый массив, который соответствует текущему разбиению клеток в изломанном профиле на компоненты связности. Если всегда, идя слева направо по профилю, выбирать в качестве номера очередной компоненты минимальное неиспользованное целое неотрицательное число, максимальное количество различных достижимых состояний для $$$m = 10$$$ оказывается $$$\sim 7\,500$$$. Итоговое время работы равно $$$O(n \cdot m \cdot S \cdot m)$$$, где $$$S \approx 7\,500$$$ — число различных состояний.