1.题目基本信息

1.1.题目描述

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

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

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

1.2.题目地址

https://leetcode.cn/problems/transform-to-chessboard/description/

2.解题方法

2.1.解题思路

逆向推理。

从目标状态向初始状态进行转换。经过几次模拟可以看出，逆向移动得到的网格的共同性质：每行或每列的0和1的个数差绝对值不会超过1；移动之后，每行和第一行要么完全相同，完全完全相反，列同理。第2个性质和第1个性质分别在形和数上保证能够移动成功

2.2.解题步骤

第一步，根据第1个性质和第2个性质排除不能转移到"棋盘"状态的情况

• 1.1.第1行统计与判断

• 1.2.第一列统计与判断

• 1.3.判断行列的非同即反性（如果行非同即反，则列也可以保证）

第二步，计算最少交换次数。仔细观察可以看出每行或者每列的交换具有等价性，所以可以通过第一行和第一列的最小交换次数计算总最小交换次数。列的交换对行的最小交换次数不会有影响（完全不同的两行，分别转为为0xxx和1xxx的最小转次数是相等的）。定义diff为行列与目标行列元素不同的位置的个数，如果行列数为偶数，最小转移次数为(diff,n-diff)//2；如果行列数为奇数，例如每行中1的个数比0的个数多1，则为转换为1010...1状态的最小转换次数，算diff//2

第三步，最终的结果为calcMinSwapCnt(firstRow)+calcMinSwapCnt(firstCol)

3.解题代码

python代码

class Solution:
    def movesToChessboard(self, board: List[List[int]]) -> int:
        # 思路：逆向推理。从目标状态向初始状态进行转换。经过几次模拟可以看出，逆向移动得到的网格的共同性质：每行或每列的0和1的个数差绝对值不会超过1；移动之后，每行和第一行要么完全相同，完全完全相反，列同理。第2个性质和第1个性质分别在形和数上保证能够移动成功
        # 参考：灵神-https://leetcode.cn/problems/transform-to-chessboard/solutions/2997293/tu-jie-ni-xiang-si-wei-pythonjavaccgojsr-mixb/?envType=problem-list-v2&envId=3yidzXie
        n = len(board)
        # 第一步，根据第1个性质和第2个性质排除不能转移到"棋盘"状态的情况
        # 1.1.第1行统计与判断
        firstRow = board[0]
        cnt1 = [0] * 2
        for v in firstRow:
            cnt1[v] += 1
        if abs(cnt1[1] - cnt1[0]) > 1:
            return -1
        # 1.2.第一列统计与判断
        firstCol = [board[i][0] for i in range(n)]
        cnt2 = [0] * 2
        for v in firstCol:
            cnt2[v] += 1
        if abs(cnt2[1] - cnt2[0]) > 1:
            return -1
        # 1.3.判断行列的非同即反性（如果行非同即反，则列也可以保证）
        for row in board[1:]:
            same = row[0] == firstRow[0]
            for x, y in zip(row, firstRow):
                if (x == y) != same:
                    return -1
        # 第二步，计算最少交换次数。仔细观察可以看出每行或者每列的交换具有等价性，所以可以通过第一行和第一列的最小交换次数计算总最小交换次数。列的交换对行的最小交换次数不会有影响（完全不同的两行，分别转为为0xxx和1xxx的最小转次数是相等的）。定义diff为行列与目标行列元素不同的位置的个数，如果行列数为偶数，最小转移次数为(diff,n-diff)//2；如果行列数为奇数，例如每行中1的个数比0的个数多1，则为转换为1010...1状态的最小转换次数，算diff//2
        def calcMinSwapCnt(arr):
            cnts = [0] * 2
            for num in arr:
                cnts[num] += 1
            if cnts[0] == cnts[1]:
                diff = sum(arr[i] != i % 2 for i in range(n))
                return min(diff, n - diff) // 2
            else:
                if cnts[0] > cnts[1]:
                    diff = sum(arr[i] != i % 2 for i in range(n))
                else:
                    diff = sum(arr[i] == i % 2 for i in range(n))
                return diff // 2
        # 第三步，最终的结果为calcMinSwapCnt(firstRow)+calcMinSwapCnt(firstCol)
        return calcMinSwapCnt(firstRow) + calcMinSwapCnt(firstCol)

4.执行结果