UVa11349 - Symmetric Matrix (求對稱矩陣)

題目原文

題目內容
現在給你一個正方矩陣M。M這個矩陣的元素為M_ij : { 0 < i < n ,0 < j < n }。在這個問題中你必須判斷這個矩陣是否對稱(symmetric)。

定義：對稱矩陣定義為內部所有的元素皆為非負且每個元素都相對於這個矩陣的中心點對稱。 其他不滿足上述條件的矩陣皆為不對稱。
舉例來說:

你要作的只有判斷這個矩陣是否對稱。

矩陣內的元素範圍為-2³² <= M_ij <= 2³² 且 0 < n <= 100。


輸入說明:
輸入的第一列包含一個數字T<=300，代表測資的數量。之後的每一組測試資料的第一列包含一個數值n，代表這個正方矩陣的維度。接下來的n列即為這個矩陣內的元素數值，每個數字都會以一個空白字元隔開。

輸出說明:
對每一筆測試資料輸出一行"Test #t: S"，t為第幾筆測試資料的編號，而S代表"Symmetric"或"Non-symmetric"兩種字串，取決於輸入的矩陣是否為對稱矩陣。


Sample Input
2
N = 3
5 1 3
2 0 2
3 1 5
N = 3
5 1 3
2 0 2
0 1 5

Sample Output
Test #1: Symmetric.
Test #2: Non-symmetric.

解法
在還沒開始之前要知道這個題目有兩個陷阱，第一個是對稱矩陣的元素值必須全部非負，但輸入的值包含負數。
第二是元素的範圍為-2³² <= Mij <= 2³²，超出int的範圍(-2³¹ <= int <= 2³¹-1)，必須使用long long處理。

因為本題所定義的對稱矩陣是所有的元素相對於中心點對稱，因此若將此種矩陣沿著每一列(row)拉成一維，會發現這個一維的數列會形成迴文 (palindrome)。
以範例輸入的第一個陣列為例，沿著每一列由左至右拉成一維即"5 1 3 2 0 2 3 1 5"。所以其實除了可以使用二維陣列去逐一比對相對位置之外，也可以判斷這些輸入的元素值是否形成迴文。

一個簡單的方法是準備兩個長度相同的一維陣列，一個在輸入的時候照順序從[0]往後存，另一個反序從[n*n-1]往回存，最後判斷這兩個陣列是否相同。
(以上資料來源:冰塊的UVa解題冷藏庫與大學程式能力檢定Collegiate Programming Examination(CPE))

程式碼解答

#include <stdio.h>
int main()
{
 int t, n;
 
 scanf("%d\n", &t);//有幾筆資料
 for(int i=1; i<=t; i++)//看幾筆資料運行幾次，外加題目要的計算標題
 {
  scanf(" N = %d\n", &n);//這裡很重要很重要N前面一定要有空格不然會錯
  
  long long a[n*n];
  
  for(int j=0; j<n*n; j++)//讀入資料
   scanf("%lld", &a[j]);
   
  int key=1;
  
  int last=n*n-1;
  
  for(int k=0; k<n*n; k++)//判斷
  {
   if(k>=last ||key==0)
    break;
    
   if(a[k]<0 || (a[k]!=a[last-k]))
    key=0;
   
  }
  
  printf("Test #%d: %s.\n", i, key ? "Symmetric" : "Non-symmetric");
  
  
 }
}

程式碼打包:解法一 解法二 解法三