ccsp/src/leetcode/p3548/Solution.java

package leetcode.p3548;

import java.util.HashMap;
import java.util.Map;

/**
 * @ProjectName: LeetCode
 * @FileName: Solution
 * @Author: 杨逸
 * @Data:2026/3/26 18:07
 * @Description: https://leetcode.cn/problems/equal-sum-grid-partition-ii/description/
 * 3548. 等和矩阵分割 II
 */
public class Solution {
    public boolean canPartitionGrid(int[][] grid) {
        /**
         * 枚举分界线
         * 当前值sum大于total/2时,判断能否通过减去一个单元格使的sum=total/2
         * 使用两个哈希表记录分界线前后的元素
         * 垂直分割时将矩阵旋转即可
         * 当只有一列时,只有第一行和最后一行可以减去
         * 只有一行时,只能减去这行的两端
         */
        long total = 0;
        Map<Long,Integer> suffixMap = new HashMap<>();
        for (int[] ints : grid) {
            for (int v : ints) {
                total += v;
                Integer count = suffixMap.getOrDefault((long)v, 0);
                count++;
                suffixMap.put((long)v,count);
            }
        }
        return check(grid,total, new HashMap<>(suffixMap)) || check(rotate(grid),total,new HashMap<>(suffixMap));
    }

    private boolean check(int[][] grid, long total, Map<Long, Integer> suffixMap) {
        Map<Long,Integer> prefixMap = new HashMap<>();
        long sum = 0;
        for (int i = 0; i < grid.length-1; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                int v = grid[i][j];
                sum += v;
                Integer count = prefixMap.getOrDefault((long)v, 0);
                count++;
                prefixMap.put((long)v,count);
                count = suffixMap.get((long)v) - 1;
                if (count == 0) {
                    suffixMap.remove((long)v);
                } else {
                    suffixMap.put((long)v,count);
                }
            }

            if (sum * 2 == total) {
                //just right
                return true;
            }else if (sum * 2 > total) {
                //subtract prefix
                long temp = total - sum;
                long d = sum - temp;
                if (grid[0].length == 1){
                    //only one colum
                    if (grid[0][0] == d || grid[i][0] == d) {
                        return true;
                    }
                }else if(i==0){
                    //only one line
                    if (grid[0][0] == d || grid[0][grid[0].length-1] == d) {
                        return true;
                    }
                } else{
                    if (!prefixMap.getOrDefault(Long.valueOf(d +""),0).equals(0)) {
                        return true;
                    }
                }
            }else{
                //subtract suffix
                long temp = total - sum;
                long d = temp - sum;
                if (grid[0].length == 1) {
                    if (grid[i+1][0] == d || grid[grid.length-1][0] == d) {
                        return true;
                    }
                }else if(i==grid.length-2){
                    if (grid[i+1][0] == d || grid[i+1][grid[0].length-1] == d) {
                        return true;
                    }
                } else{
                    if (!suffixMap.getOrDefault(Long.valueOf(d +""),0).equals(0)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    private int[][] rotate(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] result = new int[n][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                result[j][m - 1 - i] = grid[i][j];
            }
        }
        return result;
    }
}