目标
给你一个由正整数组成的 m x n 矩阵 grid。你的任务是判断是否可以通过 一条水平或一条垂直分割线 将矩阵分割成两部分，使得：
- 分割后形成的每个部分都是 非空 的。
- 两个部分中所有元素的和 相等 ，或者总共 最多移除一个单元格 （从其中一个部分中）的情况下可以使它们相等。
- 如果移除某个单元格，剩余部分必须保持 连通 。
如果存在这样的分割，返回 true；否则，返回 false。
注意： 如果一个部分中的每个单元格都可以通过向上、向下、向左或向右移动到达同一部分中的其他单元格，则认为这一部分是 连通 的。
示例 1：
输入： grid = [[1,4],[2,3]]
输出： true
解释：
在第 0 行和第 1 行之间进行水平分割，结果两部分的元素和为 1 + 4 = 5 和 2 + 3 = 5，相等。因此答案是 true。
示例 2：
输入： grid = [[1,2],[3,4]]
输出： true
解释：
在第 0 列和第 1 列之间进行垂直分割，结果两部分的元素和为 1 + 3 = 4 和 2 + 4 = 6。
通过从右侧部分移除 2 （6 - 2 = 4），两部分的元素和相等，并且两部分保持连通。因此答案是 true。
示例 3：
输入： grid = [[1,2,4],[2,3,5]]
输出： false
解释：
在第 0 行和第 1 行之间进行水平分割，结果两部分的元素和为 1 + 2 + 4 = 7 和 2 + 3 + 5 = 10。
通过从底部部分移除 3 （10 - 3 = 7），两部分的元素和相等，但底部部分不再连通（分裂为 [2] 和 [5]）。因此答案是 false。
示例 4：
输入： grid = [[4,1,8],[3,2,6]]
输出： false
解释：
不存在有效的分割，因此答案是 false。
说明：
- 1 <= m == grid.length <= 10^5
- 1 <= n == grid[i].length <= 10^5
- 2 <= m * n <= 10^5
- 1 <= grid[i][j] <= 10^5
思路
有一个 m x n 矩阵，判断能否用一条水平线或者垂线将矩阵分割成非空的两部分使得它们的元素和相等。允许进行至多一次操作，选择任一部分删除一个单元格，要求删除后这部分仍保持连通。
与 3546.等和矩阵分割I 相比，本题允许进行一次操作，在保证连通性的前提下删掉一个单元格。
先考虑水平分割，垂直分割只需将矩阵旋转 90° 即可。计算所有元素和 totalSum，按行遍历矩阵，累加当前元素和 curSum，如果要删掉已访问过的某一元素 x，需要满足 curSum - x == totalSum - curSum，当然也可能是删掉另一部分，只需将矩阵上下翻转即可。
删除单元格要保证连通性，如果矩阵只有 1 列，那么只能删除最上面的或者切线上面一个单元格。如果水平切完上面部分只有一行，那么只能删除第一个或者最后一个单元格。其余情况可以任意删除单元格。使用哈希集合记录访问过的元素值，除了上面的特殊情况，只要 x 在哈希集合中就说明是合法分割。
这个题目的思想就是抽象、变形、统一处理逻辑。
代码
/**
* @date 2026-03-26 10:28
*/
public class CanPartitionGrid3548 {
public boolean canPartitionGrid(int[][] grid) {
long totalSum = 0L;
for (int[] row : grid) {
for (int num : row) {
totalSum += num;
}
}
return cut(grid, totalSum) || cut(rotate(grid), totalSum);
}
public boolean cut(int[][] grid, long totalSum) {
if (check(grid, totalSum)) {
return true;
}
return check(flip(grid), totalSum);
}
public boolean check(int[][] grid, long totalSum) {
int m = grid.length;
int n = grid[0].length;
Set<Long> set = new HashSet<>();
set.add(0L);
long prefix = 0L;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
set.add((long) grid[i][j]);
prefix += grid[i][j];
}
long x = prefix * 2 - totalSum;
if (i == 0) {
if (x == grid[0][0] || x == grid[0][n - 1] || x == 0) {
return true;
}
} else if (n == 1) {
if (x == grid[0][0] || x == grid[i][0] || x == 0) {
return true;
}
} else if (set.contains(x)) {
return true;
}
}
return false;
}
public int[][] rotate(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] res = new int[n][m];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
res[j][i] = grid[i][j];
}
}
return res;
}
public int[][] flip(int[][] grid) {
int m = grid.length;
for (int i = 0; i < m / 2; i++) {
int[] tmp = grid[m - i - 1];
grid[m - i - 1] = grid[i];
grid[i] = tmp;
}
return grid;
}
}
性能
