题目描述
矩阵
1 7 2 4
3 6 2 8
2 1 2 3
坐标(1,3) 到 (3,4)之间的和2+4+2+8+2+3=21
算法1
O(n^2)
主要解决两个问题:
1、如何求左上角Sij的区域和
2、如何利用Sij 求区域之间的和
#1、如何求Sij左上角的所有元素和
#1、如何求Sij左上角的所有元素和
def S(nums, n, m):
s = [[0]*(m+1) for i in range(n+1)]
for i in range(1,n+1):
for j in range(1,m+1):
s[i][j] = nums[i-1][j-1] + s[i-1][j] + s[i][j-1] - s[i-1][j-1]
return s
#求区域和有公式s[x1,y1,x2,y2]=s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]
if __name__=="__main__":
n, m, q = [int(i) for i in input().split()]
nums = []
for _ in range(n):
nums.append([int(i) for i in input().split()])
s = S(nums, n, m)
ans = []
for _ in range(q):
x1,y1,x2,y2 = [int(i) for i in input().split()]
#2、求区域和
ans.append(s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1])
print('\n'.join(map(str,ans)))