この問題は、それぞれの ? に B または W を割り当てて、

• \(c_{1,1}\) が B で \(c_{1,2}\) が W なら \(1\) 点得る
• \(c_{1,1}\) が W で \(c_{1,2}\) が B なら \(1\) 点得る
• \(c_{1,1}\) が B で \(c_{2,1}\) が W なら \(1\) 点得る
• \(c_{1,1}\) が W で \(c_{2,1}\) が B なら \(1\) 点得る
• \(c_{1,2}\) が B で \(c_{1,3}\) が W なら \(1\) 点得る
  \(\quad\vdots\)

といった条件の元で点数を最大化する問題と言うことができます。
このような形の問題はあるグラフの最小カットに帰着して解くことがあります。

関連資料 : https://www.slideshare.net/shindannin/project-selection-problem
(燃やす埋める問題, Project Selection Problem で調べてみましょう)

まず、 \(2N(N-1)\) 点先に得られるとして、「\(1\) 点得る」を「\(1\) 点失う」に変換します。

• \(c_{1,1}\) が B で \(c_{1,2}\) が B なら \(1\) 点失う
• \(c_{1,1}\) が W で \(c_{1,2}\) が W なら \(1\) 点失う
• \(c_{1,1}\) が B で \(c_{2,1}\) が B なら \(1\) 点失う
• \(c_{1,1}\) が W で \(c_{2,1}\) が W なら \(1\) 点失う
• \(c_{1,2}\) が B で \(c_{1,3}\) が B なら \(1\) 点失う
  \(\quad\vdots\)

しかし、この形では最小カットに帰着することができないので、グリッドが \(2\) 部グラフであることに注目し、\(i + j\) が奇数であるような \(c_{i,j}\) について、B と W を反転します。

• \(c_{1,1}\) が B で \(c_{1,2}\) が W なら \(1\) 点失う
• \(c_{1,1}\) が W で \(c_{1,2}\) が B なら \(1\) 点失う
• \(c_{1,1}\) が B で \(c_{2,1}\) が W なら \(1\) 点失う
• \(c_{1,1}\) が W で \(c_{2,1}\) が B なら \(1\) 点失う
• \(c_{1,2}\) が W で \(c_{1,3}\) が B なら \(1\) 点失う
  \(\quad\vdots\)

入力で B や W が指定されている場合、非常に大きな定数 \(INF\) を用いて

• \(c_{i, j}\) が B なら \(INF\) 点失う

などと条件を追加すれば ? であるものとして扱えます。

これで最小カットに帰着することができます。具体的には以下のようにすると良いです。

• 頂点 \((i, j)\) から頂点 \((i, j + 1)\) に容量 \(1\) の辺を張る
• 頂点 \((i, j)\) から頂点 \((i + 1, j)\) に容量 \(1\) の辺を張る
• 頂点 \((i, j)\) から頂点 \((i, j - 1)\) に容量 \(1\) の辺を張る
• 頂点 \((i, j)\) から頂点 \((i - 1, j)\) に容量 \(1\) の辺を張る
• B と W の反転を行った後 \(c_{i,j}\) が B であれば、頂点 \(S\) から頂点 \((i, j)\) に容量 \(INF\) の辺を張る
• B と W の反転を行った後 \(c_{i,j}\) が W であれば、頂点 \((i, j)\) から頂点 \(T\) に容量 \(INF\) の辺を張る
• \(S\) から \(T\) への最小カットの容量を求める。これは、\(S\) から \(T\) への最大フローの流量と等しい。

計算量は、 Dinic 法を用いれば \(O(N^3)\) です。
実装には AC Library の maxflow を利用できます。

回答例 (C++)

回答例 (Python)