【算法】798. 差分矩阵

题目

798. 差分矩阵
思路

实质是二维差分，构造数组b，a为b的前缀和，也要用到前缀和的内容，求出数组b之后用b表现a，和一维差分思路雷同，差别之处是在加减c时二维要复杂一些。
代码

1. #include<iostream>
2. using namespace std;
3. const int N=1010;
4. int a[N][N],b[N][N];
5. void insert(int x1,int y1,int x2,int y2,int c)
6. {
7.     b[x1][y1]=b[x1][y1]+c;
8.     b[x2+1][y1]=b[x2+1][y1]-c;
9.     b[x1][y2+1]=b[x1][y2+1]-c;
10.     b[x2+1][y2+1]=b[x2+1][y2+1]+c;
11. }
12. int main()
13. {
14.     int n,m,q;
15.     scanf("%d %d %d",&n,&m,&q);
16.     for(int i=1;i<=n;i++)
17.     {
18.         for(int j=1;j<=m;j++)
19.         {
20.             scanf("%d",&a[i][j]);
21.         }
22.     }
23.     for(int i=1;i<=n;i++)
24.     {
25.         for(int j=1;j<=m;j++)
26.         {
27.             b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
28.         }
29.     }
30.     while(q--)
31.     {
32.         int x1,y1,x2,y2,c;
33.         cin>>x1>>y1>>x2>>y2>>c;
34.         insert(x1,y1,x2,y2,c);
35.     }
36.     for(int i=1;i<=n;i++)
37.     {
38.         for(int j=1;j<=m;j++)
39.         {
40.             a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
41.         }
42.     }
43.     for(int i=1;i<=n;i++)
44.     {
45.         for(int j=1;j<=m;j++)
46.         {
47.             printf("%d ",a[i][j]);
48.         }
49.         printf("\n");
50.     }
51.     return 0;
52. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。