解法のうち、操作不変量を見出すところまでは公式解説と同様です。それ以降の解の構築について、本問を最小費用流問題と解釈し、処理を機械的に行う方法を説明します。

入力として与えられた \(H \times W\) 行列 \(A\) について、\(i + j\) が奇数である \(A_{ij}\) についてのみ値を \(-1\) 倍した \(H \times W\) 行列 \(C\) を考えます。\(C\) の \(i\) 行目の要素の総和を \(f_i\) \((1 \le i \le H)\)、 \(j\) 列目の要素の総和を \(g_j\) \((1 \le j \le W)\) とおきます。本問題の目標は、 \(f_i\) と \(g_j\) の値を全ての \(i\) と \(j\) について一定に保ちつつ、目的関数 \(\sum_{i, j} \left| C_{ij} \right|\) の値を最小化することです。

ここで、\(H + W\) 頂点 \(u_1, \dots, u_H, v_1, \dots, v_W\) からなる二部グラフと、その上のフローを考えます。頂点 \(u_i\) \((1 \le i \le H)\) には湧き出し \(f_i\) を（\(f_i < 0\) の場合は吸い込みに対応します）、頂点 \(v_j\) \((1 \le j \le W)\) には吸い込み \(g_j\) をそれぞれ設定し、各頂点 \((u_i , v_j)\) 間について \(u_i \rightarrow v_j\) と \(v_j \rightarrow u_i\) の両方向に容量 \(+\infty\), コスト \(1\) の辺を張ります。このグラフにおける最小費用循環流を求めれば、そのコストが本問題で求めたいコストの値となり、更に \(u_i\) から \(v_j\) 方向への（符号付の）流量が（最適解の一つにおける）\(C_{ij}\) の値に対応します。

最小費用流問題を解く各種アルゴリズムについて、本問題の制約において実行時間制限に十分間に合うことを理論的な解析から確認するのは難しいですが、ネットワーク単体法などの実用上高速なアルゴリズムを使用することで本問題で予め用意されたテストケースに対しては十分高速に解を求めることが可能です。

• 実装例 (C++, 230 ms 程度) : コストスケーリング法による実装。
• 実装例 (C++, 1070 ms 程度) : 理論的な保証は（今の筆者の知る限り）ありませんが、AC Library の mcf_graph を使用した場合でも本解説執筆時点で用意されているテストケースに対しては実行時間制限に間に合うようです。