g004 - 社區熱門度 (Popularity)
題目描述
題目給定一個 n x m 的矩陣，矩陣中的每個元素代表一個社區的熱門度。如果一個社區的熱門度為 0，則該社區的熱門度會被設定為其相鄰（上、下、左、右）社區熱門度的平均值。題目要求輸出更新後的矩陣。
解題思路
這題的解題思路是模擬題目描述的過程。首先，讀取輸入的矩陣。然後，遍歷矩陣中的每個元素。如果該元素的值為 0，則計算其相鄰元素的平均值，並將該元素的值更新為該平均值。最後，輸出更新後的矩陣。在計算平均值時，需要注意只考慮存在（非 0）的相鄰元素，並計算相鄰元素的個數，以避免除以零的錯誤。
複雜度分析
- 時間複雜度: O(n*m)，因為需要遍歷整個矩陣兩次。
- 空間複雜度: O(n*m)，因為需要額外一個矩陣
ans來儲存更新後的結果。
程式碼
#include <iostream>
using namespace std;
int a[11][11],n,m,ans[11][11];
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
cin >> a[i][j];
ans[i][j]=a[i][j];
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(a[i][j]==0){
int t=0,c=0;
if(a[i+1][j]){
++t;
c+=a[i+1][j];
}
if(a[i-1][j]){
++t;
c+=a[i-1][j];
}
if(a[i][j+1]){
++t;
c+=a[i][j+1];
}
if(a[i][j-1]){
++t;
c+=a[i][j-1];
}
if(t!=0)ans[i][j]=c/t;
}
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j)
cout << ans[i][j] << " ";
cout << '\n';
}
}