T2 小美的平衡矩阵(25分) - 美团编程题 题解

考试平台： 牛客网

题目类型： 30道单选题（60分）+ 2 道编程题 （15分 + 25分）

考试时间： 2024-03-09 （两小时）

题目描述

小美拿到了一个n*n的矩阵，其中每个元素是 0 或者 1。
小美认为一个矩形区域是完美的，当且仅当该区域内 0 的数量恰好等于 1 的数量。
现在，小美希望你回答有多少个i*i的完美矩形区域。你需要回答$1\le i\le n$的所有答案。

输入描述

第一行输入一个正整数n ，代表矩阵大小。
接下来的n行，每行输入一个长度为n的 01 串，用来表示矩阵。
$1\le n\le 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] * (n+1) for _ in range(n)]
for r in range(n):for i, v in enumerate(grid[r]):if v == "1":psum[r][i+1] = psum[r][i] + 1else:psum[r][i+1] = 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))