h027 - 202001_2 矩陣總和
題目描述
題目要求在一個大的矩陣 B 中尋找與小矩陣 A 距離不超過 r 的子矩陣的數量，並找出這些子矩陣中總和與 A 差異最小的那個。矩陣的距離定義為對應位置元素值不相同的數量。
解題思路
此題採用暴力解法。首先讀取小矩陣 A 的所有元素並計算其總和。然後，遍歷大矩陣 B 的所有可能的子矩陣，其大小與 A 相同。對於每個子矩陣，計算它與 A 的距離（不同元素個數），如果距離小於等於 r，則增加符合條件的子矩陣數量，並計算該子矩陣的總和與 A 總和的差的絕對值，更新最小差值。最後，輸出符合條件的子矩陣數量和最小差值。如果沒有找到符合條件的子矩陣，則輸出 0 和 -1。
複雜度分析
- 時間複雜度: O(nms*t) 其中 n 和 m 是大矩陣 B 的大小，s 和 t 是小矩陣 A 的大小。因為需要遍歷大矩陣的所有可能的子矩陣，並且對於每個子矩陣，需要比較它與小矩陣 A 的所有元素。
- 空間複雜度: O(st + nm) 主要用於儲存小矩陣 A 和大矩陣 B。
程式碼
#include <iostream>
using namespace std;
int a[105][105],b[105][105],s,t,n,m,r,tt,ansx,ansy=10000000;
int main(){
cin >> s >> t >> n >> m >> r;
for(int i=0;i<s;++i){
for(int j=0;j<t;++j){
cin >> a[i][j];
tt+=a[i][j];
}
}
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
cin >> b[i][j];
for(int i=0;i<n-s+1;++i){
for(int j=0;j<m-t+1;++j){
int ct=0,tot=0;
for(int ii=0;ii<s;++ii){
for(int jj=0;jj<t;++jj){
if(a[ii][jj]!=b[i+ii][j+jj]){
++ct;
}
tot+=b[i+ii][j+jj];
}
}
if(ct<=r){
++ansx;
ansy=min(ansy,abs(tot-tt));
}
}
}
if(ansx)
cout << ansx << "\n" << ansy ;
else
cout << "0\n-1";
}