782. Transform to Chessboard

https://leetcode.com/problems/transform-to-chessboard/

题目解释

你会得到一个n*n大小的表格，内容不是0就是1，每一次都可以互换两个row或两个col，请把这个表格变成西洋棋盘的样式，也就是每个0和1不相临。

回传需要互换几次，如果无法变成西洋棋盘样式则回传-1

example

解法

• 这题超难，目前答案来不及消化，先卡位
• 9/27 补上

首先，要能排成西洋棋盘样式需要符合下面条件:

1. 所有的表格中的row只有两种样式，和任一row相同或和任一row完全相反；这同样适用於column，不过我们不用两样都检查，只要row或colume符合规则，另一个就同样符合规则

2. 每个row的"1"和"0"的数量要一样(表格长宽为偶数)或是差一个(表格长宽为奇数)

符合西洋棋盘样式的row有两种样式10101...和01010...，至於要交换几次才能变成西洋棋盘则如下:

1. 分别计算目前最外边的row和column与 0 1 交错的样式有几格不同，例如10010和01010有2格不同，和10101则有3格不同

2. 我们没办法把目前样式变成有奇数个不同的那种样式，所以第1点那种3格不同的样式就不考虑了；如果都是差偶数个的话，选短的那个

3. 最後把row和colume的差加起来，因为我们是2个2个交换，所以最後要除以2

程序码

class Solution:
    def movesToChessboard(self, board: List[List[int]]) -> int:
        
        n=len(board)
        
        rows = []
        for i in board:
            rows.append(''.join(map(str, i)))
        
        count_row = Counter(rows)
        keys = list(count_row)
        
        if len(keys) != 2: return -1 
        # 只能有两种版型
        if abs(count_row[keys[0]] - count_row[keys[1]]) > 1: return -1 
        # 版型数量不是刚好，就是差一个
        if abs(keys[0].count('0') - keys[0].count('1')) > 1: return -1 
        # 每个版型的0和1数量不是刚好，就是差一个
        if any(a == b for a, b in zip(*keys)): return -1
        # 两个版型当然不能长的一模一样
        
        
        patt1 = ([0, 1]*(n//2+1))[:n] # 101010...
        patt2 = ([1, 0]*(n//2+1))[:n] # 010101...
        #两种西洋棋盘样式
        
        diffr1, diffr2, diffc1, diffc2 = 0,0,0,0
        for a, b in zip(board[0], patt1):
            if a != b:
                diffr1 += 1
                # row和西洋棋盘样式1差几个
                
        for a, b in zip(board[0], patt2):
            if a != b:
                diffr2 += 1
                # row和西洋棋盘样式2差几个
        
        for a, b in zip(list(board[i][0] for i in range(n)), patt1):
            if a != b:
                diffc1 += 1
                # column和西洋棋盘样式1差几个
            
        for a, b in zip(list(board[i][0] for i in range(n)), patt2):
            if a != b:
                diffc2 += 1
                # column和西洋棋盘样式2差几个
        
        cands_x = [x for x in [diffr1, diffr2] if x % 2 == 0]
        cands_y = [y for y in [diffc1, diffc2] if y % 2 == 0]
        # 差奇数个的那种不考虑
        
        
        return (min(cands_x) + min(cands_y)) // 2