3212.统计X和Y频数相等的子矩阵数量

目标

给你一个二维字符矩阵 grid，其中 grid[i][j] 可能是 'X'、'Y' 或 '.'，返回满足以下条件的子矩阵数量：

• 包含 grid[0][0]
• 'X' 和 'Y' 的频数相等。
• 至少包含一个 'X'。

示例 1：

输入： grid = [["X","Y","."],["Y",".","."]]
输出： 3

示例 2：

输入： grid = [["X","X"],["X","Y"]]
输出： 0
解释：
不存在满足 'X' 和 'Y' 频数相等的子矩阵。

示例 3：

输入： grid = [[".","."],[".","."]]
输出： 0
解释：
不存在满足至少包含一个 'X' 的子矩阵。

说明：

• 1 <= grid.length, grid[i].length <= 1000
• grid[i][j] 可能是 'X'、'Y' 或 '.'.

思路

有一个矩阵 grid，其元素为 X Y .，求满足条件的子矩阵数量。要求子矩阵包含左上角 grid[0][0]，并且至少包含一个 X，且 X 与 Y 的数量相等。

二维前缀和。

代码

/**
 * @date 2026-03-19 8:49
 */
public class NumberOfSubmatrices3212 {

    public int numberOfSubmatrices(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] xCnt = new int[m + 1][n + 1];
        int[][] yCnt = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                xCnt[i + 1][j + 1] = xCnt[i][j + 1] + xCnt[i + 1][j] - xCnt[i][j];
                yCnt[i + 1][j + 1] = yCnt[i][j + 1] + yCnt[i + 1][j] - yCnt[i][j];
                if (grid[i][j] == 'X') {
                    xCnt[i + 1][j + 1]++;
                } else if (grid[i][j] == 'Y') {
                    yCnt[i + 1][j + 1]++;
                }
            }
        }
        int res = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (xCnt[i][j] == yCnt[i][j] && xCnt[i][j] != 0) {
                    res++;
                }
            }
        }
        return res;
    }
}

性能