子矩阵的和 10.28
#include <iostream>
using namespace std;
int n,m,q;
int x1,y1,x2,y2;
int main(){
cin>>n>>m>>q;
int a[n][m],s[n][m];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
for(int i=0;i<q;i++){
cin>>x1>>y1>>x2>>y2;
cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl;
}
return 0;
}
本次代码是上节课的二维版本,核心思路依然是预处理(这for循环写死人啦)
- 假如有个n行m列的数据输入,我们首先把第一排和第一列都空出来,方便对取1的生活化场景做适应(因为当我们说从1到2的时候是包含1的,所以这个时候的前面一项在计算机中应该取得的对象是q[0],这一项给它设置成0,最后一项是q[x2],一共会有x2+1项)
- 第二部是对s[n][m]的数组做填充,每一个s[i][j]都由s[i-1][j]+s[i][j-1]-s[i-1][j-1]而来,这里不必担心下标越界,因为我们的循环是从i=1,j=1开始的
- 最后处理完成后,我们就有了一个s[][]数组,我们不必一项一项的统计,而是在s数组中找到我们需要的项目加减输出即可