798、差分矩阵
输入一个 n 行 m 列的整数矩阵,再输入 q 个操作,每个操作包含五个整数 x1,y1,x2,y2,c,其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上 c。
请你将进行完所有操作后的矩阵输出。
代码1(暴力,未通过)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1010;
int n,m,q;
int a[N][N],x1[N],x2[N],y1[N],y2[N],c[N];
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",&a[i][j]);
for(int i=0;i<q;i++)
{
scanf("%d%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i],&c[i]);
x1[i]--;
y1[i]--;
x2[i]--;
y2[i]--;
for(int j=x1[i];j<=x2[i];j++)
{
for(int k=y1[i];k<=y2[i];k++)
{
a[j][k]+=c[i];
}
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
printf("%d ",a[i][j]);
}
printf("\n");
}
}
代码2
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e3 + 10;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c)
{
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;
}
int main()
{
int n, m, q;
cin >> n >> m >> q;
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++)
{
insert(i, j, i, j, a[i][j]); //构建差分数组
}
}
while (q--)
{
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
insert(x1, y1, x2, y2, c);
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]; //二维前缀和
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
printf("%d ", b[i][j]);
}
printf("\n");
}
return 0;
}
作者:z林深时见鹿
链接:https://www.acwing.com/solution/content/27325/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。