【题目来源】
蓝桥云课：1.统计子矩阵 - 蓝桥云课
【题目描述】
给定一个 \(N×M\) 的矩阵 \(A\)，请你统计有多少个子矩阵(最小 \(1×1\)，最大 \(N×M\))满足子矩阵中所有数的和不超过给定的整数 \(K\)?
【输入】
第一行包含三个整数 \(N,M\) 和 \(K\).
之后 \(N\) 行每行包含 \(M\) 个整数，代表矩阵 \(A\).
【输出】
一个整数代表答案。
【输入样例】
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12
【输出样例】
19
【算法标签】
《蓝桥云课 2109 统计子矩阵》 #2022# #双指针# #前缀和# #省赛#
【代码详解】
n, m, k = map(int, input().split())#下标从1开始：
a = [[0]*(m+1) for i in range(n+1)]
sum = [[0]*(m+1) for i in range(n+1)]for i in range(1, n+1):a[i] = [0] + list(map(int, input().split()))#预处理二维前缀和
for i in range(1, n+1):for j in range(1, m+1):sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i][j]#求矩阵[x1,y1] - [x2,y2]所有元素之和
def get_sum(sum, x1, y1, x2, y2):return sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1]#记录和不超过K的矩阵数量
ans = 0#枚举左上角
for x1 in range(1, n+1):for y1 in range(1, m+1):#枚举右下角for x2 in range(x1, n+1):for y2 in range(y1, m+1):if get_sum(sum, x1, y1, x2, y2)<=k:ans += 1
print(ans)
【运行结果】
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12
19