1.题目
问题描述
小R手里有一个大小为 n 行 m 列的矩形蛋糕，每个小正方形区域都有一个代表美味度的整数。小R打算切割出一个正方形的小蛋糕给自己，而剩下的部分将给小S。她希望两人吃的部分的美味度之和尽量接近。
我们定义小R吃到的部分的美味度之和为 s_1，而小S吃到的部分的美味度之和为 s_2，请你帮助小R找到一个切割方案，使得 |s_1 - s_2| 的值最小。
测试样例
样例1：
输入：n = 3, m = 3, a = [[1, 2, 3], [2, 3, 4], [3, 2, 1]]
输出：
1
样例2：
输入：n = 4, m = 4, a = [[1, 2, 3, 4], [4, 3, 2, 1], [1, 2, 3, 4], [4, 3, 2, 1]]
输出：
2
样例3：
输入：n = 2, m = 2, a = [[5, 5], [5, 5]]
输出：
10
2.思路
寻找矩阵中的每个正方形块，并对块中的所有数字求和无需用前缀和，只需要遍历每个点，寻找以这个点为正方形的左上角能延展出多少个正方形即可。
3.代码
def solution(n: int, m: int, a: list) -> int:# PLEASE DO NOT MODIFY THE FUNCTION SIGNATURE# write code here# 初始化一个变量来存储最小的差值min_diff = float('inf')# 遍历所有可能的正方形切割位置和大小for i in range(n):for j in range(m):# 每个位置可以延申出去的正方形# 正方形的最小边长是1，for size in range(1, min(n - i, m - j) + 1):# 计算小R吃到的部分的美味度之和s1 = sum(a[x][y] for x in range(i, i + size) for y in range(j , j + size))# 计算小S吃到的部分的美味度之和s2 = sum(a[x][y] for x in range(n) for y in range(m)) - s1# s2 = sum(a[x][y] for x in range(n) for y in range(m) if not (i <= x < i + size and j <= y < j + size))current_diff = abs(s1 - s2)if current_diff < min_diff:min_diff = current_diffreturn min_diffif __name__ == '__main__':print(solution(3, 3, [[1, 2, 3], [2, 3, 4], [3, 2, 1]]) == 1)print(solution(4, 4, [[1, 2, 3, 4], [4, 3, 2, 1], [1, 2, 3, 4], [4, 3, 2, 1]]) == 2)print(solution(2, 2, [[5, 5], [5, 5]]) == 10)
