企业网站开发制作,淘宝推广工具,佛山网站建设优化制作公司,商务网站推广目标有哪些考试平台#xff1a; 牛客网 题目类型#xff1a; 30道单选题#xff08;60分#xff09; 2 道编程题 #xff08;15分 25分#xff09; 考试时间#xff1a; 2024-03-09 #xff08;两小时#xff09; 题目描述
小美拿到了一个n*n的矩阵#xff0c;其中每个元素是… 考试平台 牛客网 题目类型 30道单选题60分 2 道编程题 15分 25分 考试时间 2024-03-09 两小时 题目描述
小美拿到了一个n*n的矩阵其中每个元素是 0 或者 1。 小美认为一个矩形区域是完美的当且仅当该区域内 0 的数量恰好等于 1 的数量。 现在小美希望你回答有多少个i*i的完美矩形区域。你需要回答 1 ≤ i ≤ n 1\leq i \leq n 1≤i≤n的所有答案。
输入描述
第一行输入一个正整数n 代表矩阵大小。 接下来的n行每行输入一个长度为n的 01 串用来表示矩阵。 1 ≤ n ≤ 200 1\leq n \leq 200 1≤n≤200
输出描述
输出n行第i行输出 i*i的完美矩形区域的数量。
示例
输入
4
1010
0101
1100
0011输出
0
7
0
1题解 暴力枚举所有情况 在暴力枚举的情况下使用前缀和优化检验 “是否是完美矩形区域” 的方法。 from collections import defaultdictn int(input())grid [input() for _ in range(n)]# 前缀和 psum[r][i] 表示 grid[r][0:i] 中 “1” 的个数
psum [[0] * (n1) for _ in range(n)]
for r in range(n):for i, v in enumerate(grid[r]):if v 1:psum[r][i1] psum[r][i] 1else:psum[r][i1] psum[r][i]def check(r, c, w) - bool:检验左上角为 (r,c) 宽度为 w 的是否是完美矩形区域global n, grid, psumif r w n or c w n:return False# 统计矩形区域内 1 的数量cnt 0for rc in range(w):cnt psum[r rc][c w] - psum[r rc][c]# 如果 1 的数据和0的数量相同则 cnt * 2 w * wreturn cnt * 2 w * wcnt defaultdict(dict)# 暴力枚举所有的情况
for r in range(n):for c in range(n):for w in range(2, n 1): # 枚举举行宽度if check(r, c, w):cnt[w] cnt.get(w, 0) 1# 打印结果输出
for i in range(1, n 1):print(cnt.get(i, 0))
