解题思路

这道题要判断一个 0/1 方阵是不是“对称”的。

1. 什么是对称？

题目说：站在第 i 行第 j 列的学生，和站在第 j 行第 i 列的学生，性别相同，就是对称。说白了，就是把方阵沿着“主对角线”（左上到右下）对折，两边能完全重合，就是对称。

2. 怎么检查？

最简单的方法：把每个格子 (i,j) 都拿出来，和它对折后对应的格子 (j,i) 比一比：

• 只要发现一次 a[i][j] 和 a[j][i] 不一样，就说明不对称，直接输出 NO 并结束程序；
• 把所有格子都检查完，全都相等，就输出 YES。

3. 小技巧

判断的时候其实可以只检查一半的格子（比如 i<j 的那些），因为 (i,j) 和 (j,i) 是同一对，检查两遍是重复的。不过对刚学的小朋友来说，两层循环全查一遍更简单、更不容易错，反正 n<10，怎么查都很快。

4. 对照样例

样例里的方阵：第 1 行第 4 列是 1，而第 4 行第 1 列是 0，两边不一样，所以输出 NO。

参考代码

#include <iostream>
using namespace std;
int a[15][15];
int main(){
    // P4522 判断对称方阵：任意 i 行 j 列 与 j 行 i 列相等则对称
    int n;
    cin >> n;
    // 读入方阵
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin >> a[i][j];
    // 检查每一对对称位置是否相同
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(a[i][j] != a[j][i]){ // 发现不一样就不是对称方阵
                cout << "NO" << endl;
                return 0;
            }
    cout << "YES" << endl;
    return 0;
}

复杂度分析

检查的时候要遍历整个方阵，n 行 n 列共 n² 个格子，每次比较一对，所以时间复杂度是 O(n²)。题目保证 3<n<10，n 最多 9，9×9=81 次比较，非常快。

读入方阵需要一个 n×n 的二维数组，空间复杂度是 O(n²)。