グリッドを左右反転することで「グリッドの右上側が白、グリッドの左下側が黒となるように塗り替える」という問題を考えます。
そのような塗り方は白と黒の境界を考えることで「グリッドの左上の頂点から右下の頂点に至る経路」と1対1に対応します。
よって問題は「グリッドの左上の頂点から右下の頂点まで右または下へ移動して至る経路について、以下で定まるコストの最小値を求めよ。『下方向の移動それぞれについて、その行で左側にある白マスの個数と右側にある黒マスの個数の和の合計』」となります。
これは各行について黒マスの個数の累積和を予め求めておくことで、 \(DP[i][j]=(i,j)\) に至るまでのコスト、とするDPにより \(O(N^2)\) で求めることができます。

サンプル2の例