AcWing 796. 子矩阵的和(Java)
原题链接
简单
作者:
j简单
,
2021-01-21 16:23:34
,
所有人可见
,
阅读 428
import java.io.*;
public class Main{
public static void main(String args[]) throws Exception{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String s[] = bf.readLine().split(" ");
int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]), k =Integer.parseInt(s[2]);
int [][]q = new int[n+1][m+1];
int [][]sum = new int[n+1][m+1];
for(int i = 1; i <= n; i++){
String strArr[] = bf.readLine().split(" ");
for (int j = 1; j <= m; j++) q[i][j] = Integer.parseInt(strArr[j-1]);
}
//用来暂时存放每一行的前缀和
int col [] = new int[m+1];
//前缀和二维数组
for(int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
col[j] = col[j - 1] + q[i][j];
sum[i][j] = sum[i-1][j] + col[j];
//System.out.print(sum[i][j] + " ");
}
//System.out.println();
}
while( k > 0){
String p[] = bf.readLine().split(" ");
int x1 = Integer.parseInt(p[0]), y1 = Integer.parseInt(p[1]), x2 =Integer.parseInt(p[2]), y2 = Integer.parseInt(p[3]);
//画个图就知道下面公式的意义了
int res = sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 -1];
System.out.println(res);
k --;
}
}
}