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.

Examples:
Input: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
Output: 2
Explanation:
One potential sequence of moves is shown below, from left to right:

0110     1010     1010
0110 --> 1010 --> 0101
1001     0101     1010
1001     0101     0101

The first move swaps the first and second column.
The second move swaps the second and third row.


Input: board = [[0, 1], [1, 0]]
Output: 0
Explanation:
Also note that the board with 0 in the top left corner,
01
10

is also a valid chessboard.

Input: board = [[1, 0], [1, 0]]
Output: -1
Explanation:
No 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.

思路：观察，观察出思路

Intuition

After a swap of columns, two rows that were the same stay the same, and two rows that were different stay different. Since the final state of a chessboard has only two different kinds of rows, there must have originally been only two different kinds of rows.

Furthermore, these rows must have had half zeros and half ones, (except when the length is odd, where there could be an extra zero or one), and one row must be the opposite (0 changed to 1 and vice versa) of the other row. This is because moves do not change these properties either.

Similarly, the above is true for columns.

Now, because a row move followed by a column move is the same as a column move followed by a row move, we can assume all the row moves happen first, then all the column moves. (Note: it is not true that a row move followed by another row move is the same as those moves backwards.)

Since there are only two kinds of rows, we want the minimum number of moves to make them alternating; and similarly for columns. This reduces to a one dimensional problem, where we have an array like [0, 1, 1, 1, 0, 0] and we want to know the least cost to make it [0, 1, 0, 1, 0, 1] or [1, 0, 1, 0, 1, 0].

Algorithm

For each set of rows (and columns respectively), make sure there are only 2 kinds of lines in the right quantities that are opposites of each other.

Then, for each possible ideal transformation of that line, find the minimum number of swaps to convert that line to it's ideal and add it to the answer. For example, [0, 1, 1, 1, 0, 0] has two ideals [0, 1, 0, 1, 0, 1] or [1, 0, 1, 0, 1, 0]; but [0, 1, 1, 1, 0] only has one ideal [1, 0, 1, 0, 1].

In Java, we use integers to represent the rows as binary numbers. We check the number of differences with [1, 0, 1, 0, 1, 0, ...] by xoring with 0b010101010101.....01 = 0x55555555. To make sure we don't add extra large powers of 2, we also bitwise-AND by 0b00...0011...11 where there are N ones in this mask.

# -*- coding: utf-8 -*-
import collections
class Solution:
    def movesToChessboard(self, board):
        N = len(board)
        s = collections.Counter(tuple(l) for l in board)
        
        # 只能有2种行
        if len(s) != 2: return -1
        
        # 2种行是0,1相对交叉的        
        for a, b in zip(*s.keys()): 
            if a == b: return -1
        
        # 行列交换顺序无所谓，所以就先全部交换行再全部交换列veras
        col = sum(board[0][i] == i & 1 for i in range(N))  # 统计列：奇数位为1，偶数位为0的总和，也就是要交换次数的2倍
        row = sum(board[i][0] == i & 1 for i in range(N))
        
        # 判断N奇偶性
        if N % 2:
            for i in s:
                # 每一行1的总数只能是[N/2, N/2+1]中的一个
                # 2中行的总数也只能是[N/2, N/2+1]中的一个
                if sum(i) not in [N//2, N//2+1] or s[i] not in [N//2, N//2+1]: return -1
            if col & 1: col = N - col   # 第一行只能是什么什么的意思？但是为什么是判断col的奇偶性呢？
            if row & 1: row = N - row
        else:
            for i in s:
                if sum(i) != N/2 or s[i] != N / 2: return -1
            # N是偶数的话，第一行可以是2种情况，去交换次数最小的
            col = min(N - col, col)
            row = min(N - row, row)
        return (col + row) // 2

s=Solution()
#print(s.movesToChessboard([[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]))
print(s.movesToChessboard([[1,1,0],[0,0,1],[0,0,1]]))