The problem is equivalent to a maximization problem where you can assign either B or W to ? and

• Obtain \(1\) point if \(c_{1,1}\) is B and \(c_{1,2}\) is W
• Obtain \(1\) point if \(c_{1,1}\) is W and \(c_{1,2}\) is B
• Obtain \(1\) point if \(c_{1,1}\) is B and \(c_{2,1}\) is W
• Obtain \(1\) point if \(c_{1,1}\) is W and \(c_{2,1}\) is B
• Obtain \(1\) point if \(c_{1,2}\) is B and \(c_{1,3}\) is W
  \(\quad\vdots\)

and so on. Sometimes, problems in such form can be boiled down to a minimum cut of a graph.

(This is so-called “Project Selection Problem”)

First, assume that we can obtain \(2N(N-1)\) points at first, and convert “obtain \(1\) point” to “lose \(1\) point.”

• Lose \(1\) point if \(c_{1,1}\) is B and \(c_{1,2}\) is B
• Lose \(1\) point if \(c_{1,1}\) is W and \(c_{1,2}\) is W
• Lose \(1\) point if \(c_{1,1}\) is B and \(c_{2,1}\) is B
• Lose \(1\) point if \(c_{1,1}\) is W and \(c_{2,1}\) is W
• Lose \(1\) point if \(c_{1,2}\) is B and \(c_{1,3}\) is B
  \(\quad\vdots\)

However, this form cannot be boiled down to minimum cut. Observe that the grid forms a bipartite graph, and flip B and W for \(c_{i,j}\) such that \(i + j\) is odd.

• Lose \(1\) point if \(c_{1,1}\) is B and \(c_{1,2}\) is W
• Lose \(1\) point if \(c_{1,1}\) is W and \(c_{1,2}\) is B
• Lose \(1\) point if \(c_{1,1}\) is B and \(c_{2,1}\) is W
• Lose \(1\) point if \(c_{1,1}\) is W and \(c_{2,1}\) is B
• Lose \(1\) point if \(c_{1,2}\) is W and \(c_{1,3}\) is B
  \(\quad\vdots\)

When B or W is given in the input, we can add such condition that

• lose \(INF\) points if \(c_{i, j}\) is B

with a very large constant \(INF\), so that we can regard it as ?.

Now it can be transformed to min-cut problem. Specifically, follow these steps:

• Add an edge of capacity \(1\) from vertex \((i, j)\) to vertex \((i, j + 1)\)
• Add an edge of capacity \(1\) from vertex \((i, j)\) to vertex \((i + 1, j)\)
• Add an edge of capacity \(1\) from vertex \((i, j)\) to vertex \((i, j - 1)\)
• Add an edge of capacity \(1\) from vertex \((i, j)\) to vertex \((i - 1, j)\)
• If \(c_{i, j}\) is B after flipping B and W, add an edge of capacity \(INF\) from vertex \(S\) to vertex \((i, j)\)
• If \(c_{i, j}\) is W after flipping B and W, add an edge of capacity \(INF\) from vertex \((i, j)\) to vertex \(T\)
• Find the capacity of minimum cut from \(S\) to \(T\). This is equal to the maximum flow from \(S\) to \(T\).

The time complexity is \(O(N^3)\) if Dinic’s algorithm is used. For implementation, you can use maxflow in AC Library.

Sample Code (C++)

Sample Code (Python)