j062 - 11470 - Square Sums
題目描述
題目要求計算一個 n x n 的矩陣中，由外向內各個同心正方形的元素總和。輸入有多組測試資料，每組資料包含一個整數 n，表示矩陣的維度，以及一個 n x n 的矩陣。輸出格式為 "Case x: " 後跟從外到內各個同心正方形的總和，以空格分隔。
解題思路
程式碼首先讀取矩陣的維度 n。如果 n 為 0，則結束程式。然後，程式碼讀取 n x n 的矩陣元素。接著，程式碼計算每個同心正方形的總和。外層迴圈遍歷同心正方形的層數，內層迴圈計算每個同心正方形的總和。計算過程中，利用 b 陣列儲存每一層的總和，並透過差分的方式計算下一層的總和。最後，程式碼輸出每個同心正方形的總和，以空格分隔。
複雜度分析
- 時間複雜度: O(n^3)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
int n,a[11][11],b[11],ca;
int main(){
cin.tie(0); ios::sync_with_stdio(0);
for(;cin >> n;){
if(n==0)return 0;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
cin >> a[i][j];
cout << "Case " << ++ca << ":";
for(int i=0;i<n/2+n%2;++i){
b[i]=b[i+1]=0;
for(int j=i;j<n-i;++j)
for(int k=i;k<n-i;++k)
b[i]+=a[j][k];
}
int sum=0;
for(int i=n/2-1+n%2;i>=0;--i){
sum+=b[i+1];
b[i]-=sum;
}
for(int i=0;i<n/2+n%2;++i)
cout << " " << b[i];
cout << "\n";
}
}