次のような \(2 \times N^2\) 頂点の辺容量つきグラフ \(G\) を考えます。

• 頂点には \(S_{1,1},\dots,S_{N,N}\) および \(T_{1,1},\dots,T_{N,N}\) というラベルが割り振られている。
• \(S_{i,j} \to T_{i,j}\) に容量 \(c_{i,j}\) の辺が張られている。
• \((i,j)\) と \((k,l)\) がグリット上で隣接しているとき、\(S_{i,j} \to T_{k,l}\) に容量 \(\infty\) の辺が張られている。

このとき、条件を満たすように壁を建てるコストは、\(G\) 上 の\(T_{1,1}\) - \(S_{N,N}\) 間の最小カットに一致します。
最小カットは Dinic 法などのフローアルゴリズムで \(\mathrm{O}(N^6)\) 程度で計算できるので、この問題を十分高速に解くことができます。

より計算量の良い別解としてダイクストラ法を使った計算量 \(\mathrm{O}(N^2 \log N)\) の解法もありますがここでは割愛します。