🔗 UVA-11349 Symmetric Matrix

tags: `矩陣(Matrix)`

範例程式碼已於 UVA、瘋狂程設(CPE)、ZeroJudge 上皆測試通過。

題意

給定一個大小為 $n \times n$ 的矩陣 $M$ ，判斷這個矩陣是否為 對稱矩陣(symmetric matrix) 。

對稱矩陣(symmetric matrix) 的定義是，矩陣中的所有元素均為非負數，且矩陣相對於中心對稱。

約束條件

$0 < n \leq 100$
$-2^{32} \leq M_{ij} \leq 2^{32}$

思路

根據題意，由於矩陣相對於中心對稱，故 $M[i][j]$ 需要與 $M[n-i-1][n-j-1]$ 相等，且所有元素均為非負數。

故遍歷矩陣中的每個元素，檢查是否滿足上述條件即可。

但事實上，檢查是否相較於中心對稱只需要檢查上半部即可，因此可以優化為只檢查 $i \leq \lfloor \frac{n-1}{2} \rfloor$ 的元素。不過由於還是要檢查是否有負數，因此還是需要遍歷所有元素。

複雜度分析

時間複雜度： $\mathcal{O}(n^2)$
空間複雜度： $\mathcal{O}(n^2)$

T = int(input())

for kase in range(1, T+1):
    n = int(input().split()[2])
    mat = [list(map(int, input().split())) for _ in range(n)]

    flag = True
    for i in range(n):
        for j in range(n):
            # 雖然檢查是否對稱只需要檢查上半部即可，但還是要檢查是否有負數
            if mat[i][j] < 0 or mat[i][j] != mat[n - 1 - i][n - 1 - j]:
                flag = False
                break
        if not flag:
            break
    
    if flag:
        print(f"Test #{kase}: Symmetric.")
    else:
        print(f"Test #{kase}: Non-symmetric.")

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int t, kase=1, n;
    char t1, t2;
    cin >> t;
    while (t--) {
        cin >> t1 >> t2 >> n;
        // Read matrix and check if any element is negative
        vector<vector<LL>> mat(n, vector<LL>(n));
        bool flag = true;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                cin >> mat[i][j];
                if (mat[i][j] < 0) flag = false;
            }
        }
        // Check if the matrix is symmetric
        for (int i = 0; i < (n + 1) / 2 && flag; ++i) {
            for (int j = 0; j < n && flag; ++j) {
                if (mat[i][j] != mat[n - i - 1][n - j - 1])
                    flag = false;
            }
        }
        // Output
        cout << "Test #" << kase++ << ": ";
        if (flag) cout << "Symmetric." << endl;
        else cout << "Non-symmetric." << endl;
    }
    return 0;
}