变为棋盘

难度: Hard

一个 n x n 的二维网络 board 仅由 0 和 1 组成。每次移动，你能任意交换两列或是两行的位置。

返回 将这个矩阵变为 “棋盘” 所需的最小移动次数 。如果不存在可行的变换，输出 -1。

“棋盘” 是指任意一格的上下左右四个方向的值均与本身不同的矩阵。

示例 1:

输入: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
输出: 2
解释:一种可行的变换方式如下，从左到右：
第一次移动交换了第一列和第二列。
第二次移动交换了第二行和第三行。

示例 2:

输入: board = [[0, 1], [1, 0]]
输出: 0
解释: 注意左上角的格值为0时也是合法的棋盘，也是合法的棋盘.

示例 3:

输入: board = [[1, 0], [1, 0]]
输出: -1
解释: 任意的变换都不能使这个输入变为合法的棋盘。

提示：

n == board.length
n == board[i].length
2 <= n <= 30
board[i][j] 将只包含 0或 1

Submission

运行时间: 25 ms

内存: 16.0 MB

class Solution:
    def movesToChessboard(self, board: List[List[int]]) -> int:
        n = len(board)
        # Check first row and first column pattern
        for i in range(n):
            if board[0][0]^board[0][i]^board[i][0]^board[i][i] != 0:
                return -1
        
        rowSum, colSum, rowSwap, colSwap = 0, 0, 0, 0

        for i in range(n):
            rowSum += board[0][i]
            colSum += board[i][0]

            if board[i][0] == i % 2: 
                colSwap += 1
            if board[0][i] == i % 2:
                rowSwap += 1
        
        if rowSum < n // 2 or rowSum > (n + 1) // 2: return -1
        if colSum < n // 2 or colSum > (n + 1) // 2: return -1
    
        # If n is odd, we can only swap to the pattern that matches the majority
        if n % 2:
            if colSwap % 2: colSwap = n - colSwap
            if rowSwap % 2: rowSwap = n - rowSwap
        else:
            colSwap = min(n - colSwap, colSwap)
            rowSwap = min(n - rowSwap, rowSwap)
    
        # Total swaps is half of the sum (since each swap corrects two positions)
        return (colSwap + rowSwap) // 2

Explain

这个题解的思路是先检查棋盘的第一行和第一列是否满足特定的模式。如果满足，则统计第一行和第一列中 1 的数量，以及需要交换的行数和列数。如果 1 的数量不在合法范围内，则返回 -1。否则，根据棋盘大小的奇偶性，计算最小的行交换次数和列交换次数。最后返回行列交换次数之和的一半作为最小移动次数。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def movesToChessboard(self, board: List[List[int]]) -> int:
        n = len(board)
        
        # 检查第一行和第一列的模式
        for i in range(n):
            if board[0][0]^board[0][i]^board[i][0]^board[i][i] != 0:
                return -1
        
        rowSum, colSum, rowSwap, colSwap = 0, 0, 0, 0

        for i in range(n):
            rowSum += board[0][i]  # 统计第一行中 1 的数量
            colSum += board[i][0]  # 统计第一列中 1 的数量

            if board[i][0] == i % 2: 
                colSwap += 1  # 统计需要交换的列数
            if board[0][i] == i % 2:
                rowSwap += 1  # 统计需要交换的行数
        
        # 检查 1 的数量是否合法
        if rowSum < n // 2 or rowSum > (n + 1) // 2: return -1
        if colSum < n // 2 or colSum > (n + 1) // 2: return -1
    
        # 如果 n 为奇数，只能交换到与多数模式匹配的模式
        if n % 2:
            if colSwap % 2: colSwap = n - colSwap
            if rowSwap % 2: rowSwap = n - rowSwap
        else:
            colSwap = min(n - colSwap, colSwap)
            rowSwap = min(n - rowSwap, rowSwap)
    
        # 总交换次数为行列交换次数之和的一半（因为每次交换可以纠正两个位置）
        return (colSwap + rowSwap) // 2

Explore

这个异或运算用来确保棋盘的任何一个元素在其所在的行和列中与对角线上的元素保持相同的模式。在一个正常的棋盘模式中，任何两个对角线位置的元素应该是一样的，且行和列之间应该是相反的。通过检查 `board[0][0]` (左上角)、`board[0][i]` (第一行第i列)、`board[i][0]` (第i行第一列) 和 `board[i][i]` (对角线上的元素) 是否有相同的模式，我们能确定是否整个行和列遵循棋盘的交替模式。如果这个表达式的结果不为0，说明存在冲突，即棋盘的这部分不能通过简单交换达到目标模式，因此返回-1。

在一个大小为n的棋盘中，为了形成标准的棋盘模式（交替的1和0），第一行和第一列中1的数量必须非常接近n的一半。具体地，如果n是偶数，1的数量应该正好是n/2；如果n是奇数，则1的数量可以是n/2或n/2加1（即 (n+1)/2）。这是因为棋盘的两种符号（通常是1和0）需要尽可能均匀分布。如果1的数量超出这个范围，就无法通过交换行或列来达到完美的棋盘模式。

这样的检查是为了确认当前行或列是否符合目标棋盘模式中的交替模式。在一个标准的棋盘模式中，我们期望每个元素与其行和列的索引奇偶性相反（即索引为偶数时元素为0，索引为奇数时元素为1，或相反）。通过检查 `board[i][0] == i % 2` 和 `board[0][i] == i % 2`，我们可以确定当前行或列是否需要交换以符合这个模式。如果检查结果为false，说明当前行或列不符合预期的交替模式，应计入需要交换的次数。