3548. 等和网格分割 II

Hard

题目描述

给你一个 m x n 的正整数矩阵 grid。你的任务是确定是否可以进行一次水平切割或一次垂直切割，使得：

由切割形成的两个部分都非空。
两个部分中元素的和相等，或者通过最多丢弃一个单元格（从任一部分）可以使和相等。
如果丢弃一个单元格，该部分的其余部分必须保持连通。

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

注意：如果一个部分中的每个单元格都可以通过在该部分内向上、下、左、右移动到达任何其他单元格，则该部分是连通的。

示例 1：

输入：grid = [[1,4],[2,3]]
输出：true
解释：在第一行后进行水平切割，得到和为 1 + 4 = 5 和 2 + 3 = 5，相等。因此答案是 true。

示例 2：

输入：grid = [[1,2],[3,4]]
输出：true
解释：在第一列后进行垂直切割，得到和为 1 + 3 = 4 和 2 + 4 = 6。
通过从右部分丢弃 2（6 - 2 = 4），两个部分的和相等且保持连通。因此答案是 true。

示例 3：

输入：grid = [[1,2,4],[2,3,5]]
输出：false
解释：在第一行后进行水平切割，得到 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

解题思路

这道题的核心是枚举所有可能的水平和垂直切割，检查是否能通过最多丢弃一个元素使两部分和相等且保持连通。

关键观察：

连通性约束：只有在单行或单列的情况下，丢弃一个元素才可能破坏连通性
对于跨多行多列的区域，丢弃任何一个元素都不会影响连通性

解决方案：

水平切割： 枚举在第 i 行和第 i+1 行之间切割
- 上部分：前 i 行，下部分：后面的行
- 如果某部分只有一行，需特别处理连通性
垂直切割： 枚举在第 j 列和第 j+1 列之间切割
- 左部分：前 j 列，右部分：后面的列
- 如果某部分只有一列，需特别处理连通性
平衡检查：
- 不丢弃元素：两部分和直接相等
- 丢弃一个元素：从和较大的部分丢弃差值元素，且该元素存在
- 连通性检查：只有单行/单列才可能断连，丢弃的元素不能在边界

优化： 使用前缀和快速计算区域和，用哈希表统计元素频次以快速检查是否存在目标元素。

代码实现

class Solution {
public:
    bool canPartitionGrid(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        
        // Calculate prefix sums
        vector<vector<long long>> prefix(m + 1, vector<long long>(n + 1, 0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefix[i + 1][j + 1] = prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j] + grid[i][j];
            }
        }
        
        // Try horizontal cuts
        for (int i = 0; i < m - 1; i++) {
            long long top = prefix[i + 1][n];
            long long bottom = prefix[m][n] - top;
            
            if (top == bottom) return true;
            
            long long diff = abs(top - bottom);
            if (top > bottom) {
                // Check if we can remove diff from top part
                if (i == 0) { // Single row
                    for (int j = 1; j < n - 1; j++) {
                        if (grid[0][j] == diff) return true;
                    }
                } else {
                    // Multi-row, any element can be removed
                    unordered_map<int, int> count;
                    for (int r = 0; r <= i; r++) {
                        for (int c = 0; c < n; c++) {
                            count[grid[r][c]]++;
                        }
                    }
                    if (count[diff] > 0) return true;
                }
            } else {
                // Check if we can remove diff from bottom part
                if (i == m - 2) { // Single row
                    for (int j = 1; j < n - 1; j++) {
                        if (grid[m - 1][j] == diff) return true;
                    }
                } else {
                    // Multi-row, any element can be removed
                    unordered_map<int, int> count;
                    for (int r = i + 1; r < m; r++) {
                        for (int c = 0; c < n; c++) {
                            count[grid[r][c]]++;
                        }
                    }
                    if (count[diff] > 0) return true;
                }
            }
        }
        
        // Try vertical cuts
        for (int j = 0; j < n - 1; j++) {
            long long left = prefix[m][j + 1];
            long long right = prefix[m][n] - left;
            
            if (left == right) return true;
            
            long long diff = abs(left - right);
            if (left > right) {
                // Check if we can remove diff from left part
                if (j == 0) { // Single column
                    for (int i = 1; i < m - 1; i++) {
                        if (grid[i][0] == diff) return true;
                    }
                } else {
                    // Multi-column, any element can be removed
                    unordered_map<int, int> count;
                    for (int r = 0; r < m; r++) {
                        for (int c = 0; c <= j; c++) {
                            count[grid[r][c]]++;
                        }
                    }
                    if (count[diff] > 0) return true;
                }
            } else {
                // Check if we can remove diff from right part
                if (j == n - 2) { // Single column
                    for (int i = 1; i < m - 1; i++) {
                        if (grid[i][n - 1] == diff) return true;
                    }
                } else {
                    // Multi-column, any element can be removed
                    unordered_map<int, int> count;
                    for (int r = 0; r < m; r++) {
                        for (int c = j + 1; c < n; c++) {
                            count[grid[r][c]]++;
                        }
                    }
                    if (count[diff] > 0) return true;
                }
            }
        }
        
        return false;
    }
};

class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        m, n = len(grid), len(grid[0])
        
        # Calculate prefix sums
        prefix = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m):
            for j in range(n):
                prefix[i + 1][j + 1] = prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j] + grid[i][j]
        
        # Try horizontal cuts
        for i in range(m - 1):
            top = prefix[i + 1][n]
            bottom = prefix[m][n] - top
            
            if top == bottom:
                return True
            
            diff = abs(top - bottom)
            if top > bottom:
                # Check if we can remove diff from top part
                if i == 0:  # Single row
                    for j in range(1, n - 1):
                        if grid[0][j] == diff:
                            return True
                else:
                    # Multi-row, any element can be removed
                    count = {}
                    for r in range(i + 1):
                        for c in range(n):
                            count[grid[r][c]] = count.get(grid[r][c], 0) + 1
                    if count.get(diff, 0) > 0:
                        return True
            else:
                # Check if we can remove diff from bottom part
                if i == m - 2:  # Single row
                    for j in range(1, n - 1):
                        if grid[m - 1][j] == diff:
                            return True
                else:
                    # Multi-row, any element can be removed
                    count = {}
                    for r in range(i + 1, m):
                        for c in range(n):
                            count[grid[r][c]] = count.get(grid[r][c], 0) + 1
                    if count.get(diff, 0) > 0:
                        return True
        
        # Try vertical cuts
        for j in range(n - 1):
            left = prefix[m][j + 1]
            right = prefix[m][n] - left
            
            if left == right:
                return True
            
            diff = abs(left - right)
            if left > right:
                # Check if we can remove diff from left part
                if j == 0:  # Single column
                    for i in range(1, m - 1):
                        if grid[i][0] == diff:
                            return True
                else:
                    # Multi-column, any element can be removed
                    count = {}
                    for r in range(m):
                        for c in range(j + 1):
                            count[grid[r][c]] = count.get(grid[r][c], 0) + 1
                    if count.get(diff, 0) > 0:
                        return True
            else:
                # Check if we can remove diff from right part
                if j == n - 2:  # Single column
                    for i in range(1, m - 1):
                        if grid[i][n - 1] == diff:
                            return True
                else:
                    # Multi-column, any element can be removed
                    count = {}
                    for r in range(m):
                        for c in range(j + 1, n):
                            count[grid[r][c]] = count.get(grid[r][c], 0) + 1
                    if count.get(diff, 0) > 0:
                        return True
        
        return False

public class Solution {
    public bool CanPartitionGrid(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        
        // Calculate prefix sums
        long[,] prefix = new long[m + 1, n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefix[i + 1, j + 1] = prefix[i, j + 1] + prefix[i + 1, j] - prefix[i, j] + grid[i][j];
            }
        }
        
        // Try horizontal cuts
        for (int i = 0; i < m - 1; i++) {
            long top = prefix[i + 1, n];
            long bottom = prefix[m, n] - top;
            
            if (top == bottom) return true;
            
            long diff = Math.Abs(top - bottom);
            if (top > bottom) {
                // Check if we can remove diff from top part
                if (i == 0) { // Single row
                    for (int j = 1; j < n - 1; j++) {
                        if (grid[0][j] == diff) return true;
                    }
                } else {
                    // Multi-row, any element can be removed
                    var count = new Dictionary<int, int>();
                    for (int r = 0; r <= i; r++) {
                        for (int c = 0; c < n; c++) {
                            count[grid[r][c]] = count.GetValueOrDefault(grid[r][c], 0) + 1;
                        }
                    }
                    if (count.GetValueOrDefault((int)diff, 0) > 0) return true;
                }
            } else {
                // Check if we can remove diff from bottom part
                if (i == m - 2) { // Single row
                    for (int j = 1; j < n - 1; j++) {
                        if (grid[m - 1][j] == diff) return true;
                    }
                } else {
                    // Multi-row, any element can be removed
                    var count = new Dictionary<int, int>();
                    for (int r = i + 1; r < m; r++) {
                        for (int c = 0; c < n; c++) {
                            count[grid[r][c]] = count.GetValueOrDefault(grid[r][c], 0) + 1;
                        }
                    }
                    if (count.GetValueOrDefault((int)diff, 0) > 0) return true;
                }
            }
        }
        
        // Try vertical cuts
        for (int j = 0; j < n - 1; j++) {
            long left = prefix[m, j + 1];
            long right = prefix[m, n] - left;
            
            if (left == right) return true;
            
            long diff = Math.Abs(left - right);
            if (left > right) {
                // Check if we can remove diff from left part
                if (j == 0) { // Single column
                    for (int i = 1; i < m - 1; i++) {
                        if (grid[i][0] == diff) return true;
                    }
                } else {
                    // Multi-column, any element can be removed
                    var count = new Dictionary<int, int>();
                    for (int r = 0; r < m; r++) {
                        for (int c = 0; c <= j; c++) {
                            count[grid[r][c]] = count.GetValueOrDefault(grid[r][c], 0) + 1;
                        }
                    }
                    if (count.GetValueOrDefault((int)diff, 0) > 0) return true;
                }
            } else {
                // Check if we can remove diff from right part
                if (j == n - 2) { // Single column
                    for (int i = 1; i < m - 1; i++) {
                        if (grid[i][n - 1] == diff) return true;
                    }
                } else {
                    // Multi-column, any element can be removed
                    var count = new Dictionary<int, int>();
                    for (int r = 0; r < m; r++) {
                        for (int c = j + 1; c < n; c++) {
                            count[grid[r][c]] = count.GetValueOrDefault(grid[r][c], 0) + 1;
                        }
                    }
                    if (count.GetValueOrDefault((int)diff, 0) > 0) return true;
                }
            }
        }
        
        return false;
    }
}

var canPartitionGrid = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    
    // Check if removing a cell keeps section connected
    function isConnected(cells, removedCell) {
        if (cells.length <= 1) return true;
        
        const cellSet = new Set();
        for (let cell of cells) {
            if (removedCell && cell[0] === removedCell[0] && cell[1] === removedCell[1]) continue;
            cellSet.add(`${cell[0]},${cell[1]}`);
        }
        
        if (cellSet.size === 0) return false;
        
        const visited = new Set();
        const queue = [];
        const first = cellSet.values().next().value;
        queue.push(first);
        visited.add(first);
        
        while (queue.length > 0) {
            const current = queue.shift();
            const [r, c] = current.split(',').map(Number);
            
            for (let [dr, dc] of [[0,1], [0,-1], [1,0], [-1,0]]) {
                const nr = r + dr;
                const nc = c + dc;
                const neighbor = `${nr},${nc}`;
                
                if (cellSet.has(neighbor) && !visited.has(neighbor)) {
                    visited.add(neighbor);
                    queue.push(neighbor);
                }
            }
        }
        
        return visited.size === cellSet.size;
    }
    
    // Try horizontal cuts
    for (let cut = 0; cut < m - 1; cut++) {
        const topCells = [];
        const bottomCells = [];
        let topSum = 0, bottomSum = 0;
        
        for (let i = 0; i <= cut; i++) {
            for (let j = 0; j < n; j++) {
                topCells.push([i, j]);
                topSum += grid[i][j];
            }
        }
        
        for (let i = cut + 1; i < m; i++) {
            for (let j = 0; j < n; j++) {
                bottomCells.push([i, j]);
                bottomSum += grid[i][j];
            }
        }
        
        // Case 1: Equal without removing anything
        if (topSum === bottomSum) return true;
        
        // Case 2: Remove from top section
        for (let cell of topCells) {
            if (topSum - grid[cell[0]][cell[1]] === bottomSum) {
                if (isConnected(topCells, cell)) return true;
            }
        }
        
        // Case 3: Remove from bottom section
        for (let cell of bottomCells) {
            if (topSum === bottomSum - grid[cell[0]][cell[1]]) {
                if (isConnected(bottomCells, cell)) return true;
            }
        }
    }
    
    // Try vertical cuts
    for (let cut = 0; cut < n - 1; cut++) {
        const leftCells = [];
        const rightCells = [];
        let leftSum = 0, rightSum = 0;
        
        for (let i = 0; i < m; i++) {
            for (let j = 0; j <= cut; j++) {
                leftCells.push([i, j]);
                leftSum += grid[i][j];
            }
        }
        
        for (let i = 0; i < m; i++) {
            for (let j = cut + 1; j < n; j++) {
                rightCells.push([i, j]);
                rightSum += grid[i][j];
            }
        }
        
        // Case 1: Equal without removing anything
        if (leftSum === rightSum) return true;
        
        // Case 2: Remove from left section
        for (let cell of leftCells) {
            if (leftSum - grid[cell[0]][cell[1]] === rightSum) {
                if (isConnected(leftCells, cell)) return true;
            }
        }
        
        // Case 3: Remove from right section
        for (let cell of rightCells) {
            if (leftSum === rightSum - grid[cell[0]][cell[1]]) {
                if (isConnected(rightCells, cell)) return true;
            }
        }
    }
    
    return false;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	大O表示法
时间复杂度	O(m × n)
空间复杂度	O(m × n)

说明：

时间复杂度：O(m × n)，需要计算前缀和O(m × n)，枚举切割位置O(m + n)，每次检查最坏情况需要O(m × n)统计元素频次
空间复杂度：O(m × n)，主要用于存储前缀和数组和哈希表

题目描述#

解题思路#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

解题思路

代码实现

复杂度分析