登录枚举 & 二分
解法：枚举 & 二分
先按 等和矩阵分割 I 判断一遍，然后考虑删除一个格子的情况。
枚举要删除哪个格子，如何找到分割线呢？假设我们要找水平分割线，而且我们枚举的格子在分割线上方，那么我们可以计算“分割线上方的和，减去下方的和”。因为所有数都是正数，所以随着分割线往下移动，这个值会逐渐增大，因此可以用二分找到这个值第一次大于等于 $0$ 的位置。如果这个位置让值恰好等于 $0$，就是我们想要的分割线。垂直分割线同理。复杂度 $\mathcal{O}(nm\log (n + m))$。
本题比较细节的点在于连通性的处理，详见参考代码的注释。
参考代码（c++）
class Solution {
public:
bool canPartitionGrid(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
// 预处理前缀和
long long f[n + 1][m + 1];
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) f[i][j] = f[i][j - 1] + grid[i - 1][j - 1];
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) f[i][j] += f[i - 1][j];
// 求分割线上方的和，减去下方的和
// x 是要删除的格子，x > 0 说明在上方，否则在下方
auto calcH = [&](int i, int x) {
long long a = f[i][m], b = f[n][m] - a;
return a - x - b;
};
// 求分割线左方的和，减去右方的和
// x 是要删除的格子，x > 0 说明在左方，否则在右方
auto calcV = [&](int j, int x) {
long long a = f[n][j], b = f[n][m] - a;
return a - x - b;
};
// 不删除的情况，枚举水平分割线
for (int i = 1; i < n; i++) if (calcH(i, 0) == 0) return true;
// 不删除的情况，枚举垂直分割线
for (int j = 1; j < m; j++) if (calcV(j, 0) == 0) return true;
if (n == 1) {
// 只有一行的情况，枚举垂直分割线
// 为了保证连通性，此时删除的格子只能是头尾，或者和分割线相邻
for (int j = 1; j < m; j++) {
if (calcV(j, grid[0][0]) == 0) return true;
if (calcV(j, grid[0][j - 1]) == 0) return true;
if (calcV(j, -grid[0][j]) == 0) return true;
if (calcV(j, -grid[0][m - 1]) == 0) return true;
}
return false;
}
if (m == 1) {
// 只有一列的情况，枚举水平分割线
// 为了保证连通性，此时删除的格子只能是头尾，或者和分割线相邻
for (int i = 1; i < n; i++) {
if (calcH(i, grid[0][0]) == 0) return true;
if (calcH(i, grid[i - 1][0]) == 0) return true;
if (calcH(i, -grid[i][0]) == 0) return true;
if (calcH(i, -grid[n - 1][0]) == 0) return true;
}
return false;
}
// 枚举要删的格子，它在分割线上方
for (int i = 1; i < n; i++) for (int j = 1; j <= m; j++) {
// 如果上方只有一行，那么删除的格子只能在第一列或最后一列
int head = (i == 1 && j > 1 && j < m ? 2 : i), tail = n - 1;
if (head > tail) continue;
// 二分找到差值大于等于 0 的第一个位置
while (head < tail) {
int mid = (head + tail) >> 1;
if (calcH(mid, grid[i - 1][j - 1]) >= 0) tail = mid;
else head = mid + 1;
}
if (calcH(head, grid[i - 1][j - 1]) == 0) return true;
}
// 枚举要删的格子，它在分割线下方
for (int i = 2; i <= n; i++) for (int j = 1; j <= m; j++) {
// 如果下方只有一行，那么删除的格子只能在第一列或最后一列
int head = 1, tail = (i == n && j > 1 && j < m ? n - 2 : i - 1);
if (head > tail) continue;
// 二分找到差值大于等于 0 的第一个位置
while (head < tail) {
int mid = (head + tail) >> 1;
if (calcH(mid, -grid[i - 1][j - 1]) >= 0) tail = mid;
else head = mid + 1;
}
if (calcH(head, -grid[i - 1][j - 1]) == 0) return true;
}
// 枚举要删的格子，它在分割线左方
for (int i = 1; i <= n; i++) for (int j = 1; j < m; j++) {
// 如果左方只有一行，那么删除的格子只能在第一行或最后一行
int head = (j == 1 && i > 1 && i < n ? 2 : j), tail = m - 1;
if (head > tail) continue;
// 二分找到差值大于等于 0 的第一个位置
while (head < tail) {
int mid = (head + tail) >> 1;
if (calcV(mid, grid[i - 1][j - 1]) >= 0) tail = mid;
else head = mid + 1;
}
if (calcV(head, grid[i - 1][j - 1]) == 0) return true;
}
// 枚举要删的格子，它在分割线右方
for (int i = 1; i <= n; i++) for (int j = 2; j <= m; j++) {
// 如果右方只有一行，那么删除的格子只能在第一行或最后一行
int head = 1, tail = (j == m && i > 1 && i < n ? m - 2 : j - 1);
if (head > tail) continue;
// 二分找到差值大于等于 0 的第一个位置
while (head < tail) {
int mid = (head + tail) >> 1;
if (calcV(mid, -grid[i - 1][j - 1]) >= 0) tail = mid;
else head = mid + 1;
}
if (calcV(head, -grid[i - 1][j - 1]) == 0) return true;
}
return false;
}
};
