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