n*n矩阵多对称轴对称的最少数字修改次数及点组合并方案

核心思路 #

要让矩阵同时满足水平、垂直、主对角线、副对角线对称，本质是所有通过对称变换能互相映射的点必须是同一个数字。这些点构成一个等价类，我们需要把每个等价类找出来，再对每个类选出现次数最多的数字，计算修改次数总和。

具体实现步骤 #

1. 定义所有对称变换规则 #

对n×n矩阵中的任意点(i,j)（行号i、列号j从0开始），四个基础对称变换如下：

• 水平对称：(n-1-i, j)
• 垂直对称：(i, n-1-j)
• 主对角线对称：(j, i)
• 副对角线对称：(n-1-j, n-1-i)

2. 生成单个点的完整等价点集 #

对任意点(i,j)，依次应用所有可能的变换组合（包括多次变换，比如水平+垂直=中心对称），把所有不重复的点收集起来，就是这个点所在的等价类。

注意：部分点经过变换后会回到自身（比如奇数阶矩阵的中心点），这类点的等价类只有自己。

3. 遍历矩阵，批量处理等价类 #

• 创建一个n×n的visited矩阵，标记已处理的点，避免重复计算。
• 遍历每个点(i,j)：
  • 如果该点未被访问，生成其完整等价点集。
  • 统计集合中每个0-9数字的出现次数，找到出现次数最多的数字max_cnt。
  • 该类的修改次数为等价类大小 - max_cnt，累加到总修改次数中。
  • 把等价类中所有点标记为已访问。

代码示例（Python） #

def get_equivalent_points(i, j, n):
    points = set()
    # 初始点
    points.add((i, j))
    # 水平对称
    h = (n-1 - i, j)
    points.add(h)
    # 垂直对称
    v = (i, n-1 - j)
    points.add(v)
    # 主对角线对称
    d1 = (j, i)
    points.add(d1)
    # 副对角线对称
    d2 = (n-1 - j, n-1 - i)
    points.add(d2)
    # 组合变换：水平+垂直=中心对称
    hv = (n-1 - i, n-1 - j)
    points.add(hv)
    # 水平+主对角线
    hd1 = (n-1 - j, i)
    points.add(hd1)
    # 垂直+主对角线
    vd1 = (j, n-1 - i)
    points.add(vd1)
    # 返回去重后的等价点集合
    return points

def min_modify_count(matrix):
    n = len(matrix)
    visited = [[False for _ in range(n)] for _ in range(n)]
    total_mod = 0
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                eq_points = get_equivalent_points(i, j, n)
                # 统计每个数字的出现频次
                num_count = [0]*10
                for x, y in eq_points:
                    num = matrix[x][y]
                    num_count[num] += 1
                max_freq = max(num_count)
                total_mod += len(eq_points) - max_freq
                # 标记当前等价类所有点为已处理
                for x, y in eq_points:
                    visited[x][y] = True
    return total_mod

关键注意事项 #

• 变换组合要覆盖所有可能的对称映射，确保等价类完整无遗漏。
• 用集合存储等价点，自动去重，避免重复统计同一个点。
• 奇数阶矩阵的中心点，所有变换后都是自身，单独处理即可。

内容的提问来源于stack exchange，提问作者Too_Short