问题描述
给定一个 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
参考代码:
(暴力法只能通过30%测试)
N,M,K=map(int,input().split())
a=[[0] for i in range(N)]
a.insert(0,[0]*(M+1))
for i in range(1,N+1): #从a[1]1[1]开始读矩阵
a[i].extend(map(int,input().split()))
ans=0
for i1 in range(1,N+1):
for i2 in range(i1,N+1):
for j1 in range(1,M+1):
for j2 in range(j1,M+1):
sum=0
for i in range(i1,i2+1):
for j in range(j1,j2+1):
sum+=a[i][j]
if sum<=K: #当和不超过 K 时,ans + 1
ans+=1
print(ans)
方法二:前缀和、尺取法
n,m,k=map(int,input().split())
a=[[0] for i in range(n)] # 0 行全为 0
a.insert(0,[0]*(m+1)) #insert将[0]*(m+1)添加到a[0]
for i in range(1,n+1):
a[i].extend(map(int,input().split())) #读入每一行矩阵
s=[[0]*(m+1) for i in range(n+1)] #创建 n 行 m 列二维矩阵
for i in range(n+1):
for j in range(m+1):
s[i][j]=s[i-1][j]+a[i][j] #求第 j 列第 i 行上数字的前缀和
ans=0
for i1 in range(1,n+1): #暴力遍历行
for i2 in range(i1,n+1): #暴力遍历行
j1=1
z=0
for j2 in range(1,m+1): #j2 列上,i1~i2的区间和。累加得到二维区间和
z+=s[i2][j2]-s[i1-1][j2]
while z>k: #若区间和 > k,移动指针 j1
z-=s[i2][j1]-s[i1-1][j1] #后面指针前移
j1+=1
ans+=j2-j1+1 #若区间和小于 k
print(ans)
矩阵的行子区间仍用暴力二重遍历
只把列区间和用尺取法优化
1:Python insert()方法
描述
insert() 函数用于将指定对象插入列表的指定位置。
语法
insert()方法语法:
list.insert(index, obj)
参数
- index -- 对象 obj 需要插入的索引位置。
- obj -- 要插入列表中的对象。
返回值
该方法没有返回值,但会在列表指定位置插入对象。
2:Python extend()方法
描述
extend() 函数用于在列表末尾一次性追加另一个序列中的多个值(用新列表扩展原来的列表)。
语法
extend()方法语法:
list.extend(seq)
参数
返回值
该方法没有返回值,但会在已存在的列表中添加新的列表内容。