【问题描述】
给出一个n*m的矩阵,多次询问子矩阵中数字之和。
【输入格式】
第一行包含三个正整数n, m, k(n, m<=5000, k<=10000),分别表示矩阵行数和列数以及询问次数。
接下来的n行,每行包含m个整数(整数不超过10000),描述该矩阵。
接下来的k行询问,数据描述子矩阵左上角坐标(x1, y1),以及右下角坐标(x2, y2)。
【输出格式】
共k行,每行一个整数,表示询问的子矩阵数字之和。
【输入样例】
3 4 2
-8 4 10 -15
9 12 -3 5
11 -5 -7 -4
3 2 3 3
1 1 3 2
【输出样例】
-12
23
【算法思想】
计算矩阵的前缀和:s[x][y] = s[x - 1][y] + s[x][y -1] - s[x -1][y-1] + a[x][y]
计算子矩阵的和:s = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - ][y1 -1]
代码实现
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int N = 1010;
4 int a[N][N],s[N][N];
5 int main()
6 {
7 int n, m, q;
8 cin >> n >> m >> q;
9 for(int i = 1; i <= n; i++)
10 for(int j = 1; j <= m; j++)
11 {
12 scanf("%d", &a[i][j]);
13 s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
14 }
15 while(q--)
16 {
17 int x1, y1, x2, y2;
18 scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
19 printf("%dn", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
20 }
21 return 0;
22 }
3 4 2
-8 4 10 -15
9 12 -3 5
11 -5 -7 -4
3 2 3 3
1 1 3 2
原文链接: https://www.cnblogs.com/tflsnoi/p/13821456.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/204018
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!