Leetcode782：变为棋盘

题目描述：

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

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

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

代码思路：

这个代码是一个解决方案，用于计算将一个给定的二维棋盘（board）通过最少的翻转操作转换为标准国际象棋棋盘所需的最少步数。国际象棋棋盘的特点是：对于 n x n 的棋盘，当 n 是偶数时，棋盘由黑白相间的格子组成，每个格子上的数字交替为 0 和 1；当 n 是奇数时，棋盘的大部分格子按黑白交替排列，但有一个格子颜色与其他不同（通常位于棋盘的中间）。下面是代码的详细思路解析：

1. 初始化棋盘大小：
   • 首先，通过 n = len(board) 获取棋盘的边长。
2. 检查1的数量：
   • 计算棋盘上所有格子的值之和（即1的数量）cnt。
   • 如果1的数量太少（小于 n * n // 2）或太多（大于 (n * n + 1) // 2），则无法形成有效的国际象棋棋盘，返回 -1。
3. 检查行和列的唯一性：
   • 使用集合 s 存储棋盘的所有行，检查是否只有两种不同的行（对于偶数 n，这两种行分别对应全0和全1的交替模式；对于奇数 n，其中一种行会有一个额外的1或0）。
   • 如果行的种类不是2，返回 -1。
   • 使用 zip(*board) 转置棋盘并检查列的唯一性，同样，如果列的种类不是2，返回 -1。
4. 检查第一行和第一列中1的数量：
   • 分别计算第一行中偶数索引和奇数索引位置上的1的数量 a 和 b。
   • 检查这些数量是否满足条件：它们之和应该在 n // 2 和 (n + 1) // 2 之间。
   • 同样，计算第一列中偶数索引和奇数索引位置上的1的数量 c 和 d，并进行同样的检查。
5. 计算最少翻转次数：
   • 如果 n 是偶数，则为了形成标准棋盘，需要翻转的行数和列数应该是使第一行和第一列中1的数量最少的那两个值的和（因为偶数大小的棋盘可以完美地被黑白相间的格子填充）。
   • 如果 n 是奇数，则需要根据第一行和第一列中1的数量，选择是否翻转这些行或列中的某些，以使得它们符合奇数棋盘的特性（即大部分格子按黑白交替排列，但有一个格子颜色不同）。具体地，选择 a 和 c（如果它们的和等于 n // 2）或者 b 和 d（如果它们的和等于 n // 2），这样可以确保翻转后的棋盘符合奇数棋盘的规则。
6. 返回结果：
   • 根据上述逻辑计算得到的最少翻转次数 ans 即为结果。

通过这一系列的检查和计算，该代码能够确定是否可以通过最少的翻转操作将给定的棋盘转换为标准的国际象棋棋盘，并返回所需的最少翻转次数。如果无法转换，则返回 -1。

代码实现：

class Solution:
    def movesToChessboard(self, board: List[List[int]]) -> int:
        n = len(board)
        # 1 太多了或太少了
        cnt = sum(board[i][j] for i in range(n) for j in range(n))
        if cnt < n * n // 2 or cnt > (n * n + 1) // 2: return -1
        # 只有两个不同的行或列
        s = {tuple(row) for row in board}
        if len(s) != 2: return -1
        s = {col for col in zip(*board)}
        if len(s) != 2: return -1
        # 第一行、第一列 1 太多了或太少了
        a, b = sum(board[0][::2]), sum(board[0][1::2])
        if n // 2 > a + b or a + b > (n + 1) // 2: return -1
        c = sum(board[i][0] for i in range(0, n, 2))
        d = sum(board[i][0] for i in range(1, n, 2))
        if n // 2 > c + d or c + d > (n + 1) // 2: return -1
        # 偶数 求最小值和，奇数 求最多
        if n % 2 == 0:
            ans = min(a, b) + min(c, d)
        else: 
            if a + b == n // 2: ans = a
            else: ans = b
            if c + d == n // 2: ans += c
            else: ans += d
            
        return ans

 

原文地址：https://blog.csdn.net/m0_67598823/article/details/144334808

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！