对称矩阵问题解析

问题理解

我们需要判断一个 $n \times n$ 的矩阵（$n$ 为偶数）是否同时满足：

1. 左右对称：矩阵关于垂直中线对称
2. 上下对称：矩阵关于水平中线对称

换句话说，矩阵需要同时满足中心对称和轴对称。

数学定义

对于一个矩阵 $M$，如果满足：

• $M[i][j] = M[i][n-j-1]$（左右对称）
• $M[i][j] = M[n-i-1][j]$（上下对称）

那么该矩阵就是对称矩阵。

算法思路

1. 检查对称性：只需要检查矩阵的左上四分之一区域
2. 验证对称关系：对于每个元素 $M[i][j]$，检查它是否等于：
   • 水平对称点 $M[i][n-j-1]$
   • 垂直对称点 $M[n-i-1][j]$

代码实现

#include <bits/stdc++.h>  // 包含常用标准库
using namespace std;

int mp[1010][1010];  // 存储矩阵，最大尺寸1010x1010

// 判断矩阵是否对称的函数
bool issym(int mp[][1010], int n) {
    // 只需要检查矩阵的左上四分之一区域
    for(int i = 0; i < n / 2; i++) {        // 遍历上半部分行
        for(int j = 0; j < n; j++) {        // 遍历所有列
            // 检查上下对称：当前元素是否等于垂直对称位置的元素
            if(mp[i][j] != mp[n - i - 1][j]) {
                return false;  // 如果不对称，返回false
            }
            // 检查左右对称：当前元素是否等于水平对称位置的元素
            if(mp[i][j] != mp[i][n - j - 1]) {
                return false;  // 如果不对称，返回false
            }
        }
    }
    return true;  // 所有检查都通过，是对称矩阵
}

int main() {
    int t;  // 测试用例组数
    cin >> t;  // 读取测试用例数量
    
    // 处理每组测试用例
    while(t--) {
        int n;  // 矩阵大小
        cin >> n;  // 读取矩阵大小
        
        // 读取矩阵数据
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                cin >> mp[i][j];
            }
        }
        
        // 判断并输出结果
        cout << (issym(mp, n) ? "YES" : "NO") << endl;
    }
    
    return 0;  // 程序正常结束
}

算法分析

1. 时间复杂度：$O(t \times n^2)$
   • 每组测试用例需要检查 $n \times n$ 个元素
   • 但实际只检查了 $\frac{n}{2} \times n$ 个元素，因为利用了对称性
2. 空间复杂度：$O(n^2)$，用于存储矩阵

优化说明

• 只需要检查矩阵的左上四分之一区域，因为对称性保证了其他区域的对应关系
• 题目保证所有测试用例的 $n$ 总和不超过5000，因此算法效率足够

数学验证

对于位置 $(i, j)$ 的元素：

• 水平对称位置：$(i, n-j-1)$
• 垂直对称位置：$(n-i-1, j)$
• 中心对称位置：$(n-i-1, n-j-1)$

由于同时检查了水平和垂直对称，实际上也保证了中心对称。