You are given a square grid consisting of H rows and columns respectively. Each of the cells in the grid consists of either 0, 1, or 2. You are required to make the grid binary which means that the cell value should be 1 or 2. To do this task, you must replace each 2 and you can replace any 2 by either 0 or 1.
Grid value: It is the sum of XOR between all pairs of cells such that they share the side.
Your task is to replace each 2 by 1 or 0 in such a way that the grid value is maximized.
Input format
- The first line contains an integer H denoting the number of rows and columns in the grid.
- Next H lines contain H space-separated integers representing grid which are either 0, 1, or 2.
Output format
Print a single integer denoting the maximum grid value.
Constraints
1≤H≤100
Each cell's value is either 0, 1, or 2.
Here we can replace 2 at (2,1) by 1 ans 2 at (2,2) by 0. So this will result in grid [ [0,1],[1,0] ]. Grid value is is sum of xor between all pairs which share an side:
(1,1) and (1,2) => 0 XOR 1 => 1
(1,1) and (2,1) => 0 XOR 1 => 1
(2,1) and (2,2) => 1 XOR 0 => 1
(1,2) and (2,2) => 1 XOR 0 => 1
Sum of XOR over all pairs is 4, and by no replacement we can acheive an value greater than this.
Another way of replacement:
Here we can replace 2 at (2,1) by 0 ans 2 at (2,2) by 1. So this will result in grid [ [0,1],[0,1] ]. Grid value is is sum of xor between all pairs which share an side:
(1,1) and (1,2) => 0 XOR 1 => 1
(1,1) and (2,1) => 0 XOR 0 => 0
(2,1) and (2,2) => 0 XOR 1 => 1
(1,2) and (2,2) => 1 XOR 1 => 0
Sum of XOR over all pairs is 2, so this is not the optimal way.
