782. Transform to Chessboard

An N x N board contains only 0s and 1s. In each move, you can swap any 2 rows with each other, or any 2 columns with each other.

What is the minimum number of moves to transform the board into a "chessboard" - a board where no 0s and no 1s are 4-directionally adjacent? If the task is impossible, return -1.

1Examples:
2Input: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
3Output: 2
4Explanation:
5One potential sequence of moves is shown below, from left to right:
6
70110     1010     1010
80110 --> 1010 --> 0101
91001     0101     1010
101001     0101     0101
11
12The first move swaps the first and second column.
13The second move swaps the second and third row.
14
15
16Input: board = [[0, 1], [1, 0]]
17Output: 0
18Explanation:
19Also note that the board with 0 in the top left corner,
2001
2110
22
23is also a valid chessboard.
24
25Input: board = [[1, 0], [1, 0]]
26Output: -1
27Explanation:
28No matter what sequence of moves you make, you cannot end with a valid chessboard.

Note:

• board will have the same number of rows and columns, a number in the range [2, 30].
• board[i][j] will be only 0s or 1s.

Approach #1: Array. [Math]

1class Solution {
2    public int movesToChessboard(int[][] b) {
3        int N = b.length, rowSum = 0, colSum = 0, rowSwap = 0, colSwap = 0;
4        for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j)
5            if ((b[0][0] ^ b[i][0] ^ b[0][j] ^ b[i][j]) == 1) return -1;
6        for (int i = 0; i < N; ++i) {
7            rowSum += b[0][i];
8            colSum += b[i][0];
9            if (b[i][0] == i % 2) rowSwap++;
10            if (b[0][i] == i % 2) colSwap++;
11        }
12        if (rowSum != N/2 && rowSum != (N+1)/2) return -1;
13        if (colSum != N/2 && colSum != (N+1)/2) return -1;
14        if (N % 2 == 1) {
15            if (colSwap % 2 == 1) colSwap = N - colSwap;
16            if (rowSwap % 2 == 1) rowSwap = N - rowSwap;
17        } else {
18            colSwap = Math.min(N-colSwap, colSwap);
19            rowSwap = Math.min(N-rowSwap, rowSwap);
20        }
21        return (colSwap + rowSwap) / 2;
22    }
23}

Analysis:

In a valid chess board, there are 2 and only 2 kinds of rows and one is inverse to the other. For example if there is a row 0101001 in the board, any other row must be either 0101001 or 1010110.

The same for colums.

A corollary is that, any rectangle inside the board with corners top left, top right, bottom left, bottom right must be 4 zeros or 2 zeros 2 ones or 4 ones.

Another important property is that every row and column has half ones. Assume the board is N * N:

If N = 2  * K, every row and every colum has K ones and K zeros.

If N = 2 * K + 1, every row and every col has K ones and K + 1 zeros or K + 1 ones and K zeros.

Since the swap process does not break this property, for a fiven board to be valid, this property must hold.

These two conditions are necessary and sufficient condition for a calid chessboard.

Once we know it is a valid cheese board, we start to count swaps.

Basic on the property above, when we arange the first row, we are actually moving all columns.

I try to arrange one row into 01010 and 10101 and I count the number of swap.

In case of N even, I take the minimum swaps, because both are possible.

In case of N odd, I take the even swaps.

Because when we make a swap, we move 2 columns or 2 rows at the same time.

So col swaps and row swaps shoule be same here.

Reference:

https://leetcode.com/problems/transform-to-chessboard/discuss/114847/C%2B%2BJavaPython-Solution-with-Explanation