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_diff
    return min_diff

if __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)