力扣3546 等和矩阵分割 题解

题干

给你一个由正整数组成的 m x n 矩阵 grid。你的任务是判断是否可以通过 一条水平或一条垂直分割线 将矩阵分割成两部分，使得：

• 分割后形成的每个部分都是 非空 的。
• 两个部分中所有元素的和 相等 。

如果存在这样的分割，返回 true；否则，返回 false。

题解

前缀和/扫描问题

问题要求矩阵能供通过一条线分割成两部分，两部分总和相同，因此可以知道两部分一定为矩阵总和的一半，首先可以确定，总和为奇数时一定不能实现任务；然后横着从上往下切，直到相等；矩阵转置，复用横切扫描函数。

代码实现：

from typing import List

class Solution:
    def half_check(self, half, grid) -> bool:
        prefix = 0
        for i in range(len(grid) - 1):
            prefix += sum(grid[i])
            if prefix == half:
                return True
        return False

    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        total = sum(sum(row) for row in grid)
        if total % 2:
            return False

        half = total // 2
        return self.half_check(half, grid) or self.half_check(half, list(zip(*grid)))