公式解説で省略されていたダイクストラ法を使う方法を説明します。 例えば以下の壁の立て方は条件を満たします。

....
...#
..#.
..#.
.#..
.#..

左上と右下が分断されているという条件は、壁を伝って右上から左下に行けるという条件であるとも言えます。つまり、下の図で、Sから G に壁を伝ってたどり着けることが条件であると言えます。

.SSSSS
G....S
G...#S
G..#.S
G..#.S
G.#..S
G.#..S
GGGGG.

よって、これをダイクストラ法で求めれば良いです。 右上の点を始点、左下の点を終点として、壁を立てるコストの和を最小化すれば良いです。 ただし、以下の xで表される点を通らないように注意しなければいけません。

xx...S
xx...#
....#.
...#..
...#..
..#...
..#.xx
G#..xx

実装例 c++