Для вертикальных стенок: построим граф, вершинами которого являются максимальные непрерывные столбики из клеток. Скажем, что пропускная способность вершин — 1, тогда если существует поток величины 2, то нет решения. Иначе найдём все минимальные разрезы (из одной вершины) и посмотрим для них, какая нужна величина стенки. 

Ещё это решается без потока, а теми же методами, что и поиск точек сочленения, с построением дерева обхода в глубину.

Если бы стенку нужно было по условию строить от края до края — тогда ответом была бы просто высота столбика. Если не до краёв, то нужно аккуратно "подрезать": посмотреть, с каких сторон в каких местах к столбику прилегают компоненты связности со стартом и финишем, и разобрать несколько случаев, чтобы найти минимальную необходимую высоту прямоугольника.