3212. Count Submatrices With Equal Frequency of X and Y

練習日期：2026-03-19

難度：Medium

類型：Array、Matrix、Prefix Sum

📘 題目敘述

給你一個二維字元矩陣 grid，其中 grid[i][j] 只會是 'X'、'Y' 或 '.'。

請回傳符合以下條件的子矩陣數量：

  • 包含 grid[0][0]
  • 'X' 和 'Y' 的出現次數相同
  • 至少包含一個 'X'

條件限制

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

🧠 解題思路

這題最重要的一個觀察是：

題目要求子矩陣一定要包含 grid[0][0]

這代表我們要數的子矩陣，其實都一定是：

  • 左上角固定在 (0, 0)
  • 右下角是某個 (i, j)

也就是說，這題不是在數任意位置的所有子矩陣，而是在數：

  • 從 (0,0) 出發的前綴子矩陣

這樣事情就簡單很多了。

因為只要我知道每個前綴矩陣 (0,0) ~ (i,j) 裡：

  • 有幾個 'X'
  • 有幾個 'Y'

我就能直接判斷這個前綴子矩陣是否符合條件。

所以我這份程式開了兩個 prefix sum 矩陣：

  • countx[i][j]：前綴矩陣 (0,0) ~ (i,j) 中 'X' 的數量
  • county[i][j]：前綴矩陣 (0,0) ~ (i,j) 中 'Y' 的數量

接著對每個位置 (i, j) 算完之後，直接檢查：

  • countx[i][j] == county[i][j]
  • 而且 countx[i][j] > 0

如果成立，就代表：

  • 'X' 和 'Y' 數量一樣
  • 而且至少有一個 'X'

這個前綴子矩陣就要計入答案。

也就是說，這題的核心就是：

因為子矩陣必須包含 grid[0][0]，所以所有合法子矩陣都可以視為前綴矩陣。只要用 prefix sum 算出每個前綴矩陣中的 X、Y 數量，再逐格檢查即可。

所有變數

  • m：列數
  • n：行數
  • countx：二維前綴和，countx[i][j] 表示前綴矩陣中 'X' 的數量
  • county：二維前綴和，county[i][j] 表示前綴矩陣中 'Y' 的數量
  • ans：符合條件的子矩陣數量

🪜 主要流程步驟

1. 先建立兩個 prefix sum 矩陣，分別記錄 X 和 Y 的數量

int m = grid.size();
int n = grid[0].size();
vector<vector<int>> countx(m, vector<int>(n, 0));
vector<vector<int>> county(m, vector<int>(n, 0));

這裡我沒有用一個矩陣同時記錄差值，而是直接分開記：

  • countx
  • county

這樣後面判斷會比較直觀：

  • countx[i][j] == county[i][j]
  • countx[i][j] > 0

2. 先處理左上角 (0, 0)

if (grid[0][0] == 'X') {
    countx[0][0]++;
} else if (grid[0][0] == 'Y') {
    county[0][0]++;
}

這一步是在初始化 prefix sum 的起點。

因為 (0,0) 這格沒有上面和左邊可以參考，所以先單獨處理：

  • 如果是 'X'，就讓 countx[0][0] = 1
  • 如果是 'Y'，就讓 county[0][0] = 1
  • 如果是 '.'，兩個都維持 0

注意這份程式沒有在這裡直接判斷答案，因為如果只有 (0,0) 一格，想要 'X' 和 'Y' 數量一樣且至少一個 'X'，其實不可能成立。

3. 先處理第一欄，因為它只能從上面累積

int ans = 0;
for (int i = 1; i < m; i++) {
    if (grid[i][0] == 'X') {
        countx[i][0]++;
    } else if (grid[i][0] == 'Y') {
        county[i][0]++;
    }
    countx[i][0] += countx[i - 1][0];
    county[i][0] += county[i - 1][0];
    if (countx[i][0] - county[i][0] == 0 && countx[i][0] > 0) {
        ans++;
    }
}

第一欄的位置 (i,0) 沒有左邊，所以前綴和只需要從上面累加。

這段的邏輯是：

  1. 先看目前這格是不是 'X' 或 'Y'
  2. 把它加到目前這格自己的計數
  3. 再加上上面那格的 prefix sum
  4. 最後檢查這個前綴子矩陣是否符合題意

判斷條件：

  • countx[i][0] - county[i][0] == 0
    • 代表 X 和 Y 一樣多
  • countx[i][0] > 0
    • 代表至少有一個 X

4. 再處理第一列，因為它只能從左邊累積

這邊和第一欄完全對稱。

第一列的位置 (0,j) 沒有上面，所以 prefix sum 只能從左邊累積。

做完這一步後：

  • 第一列和第一欄的 prefix sum 都處理好了

5. 一般位置用二維 prefix sum 公式計算 X 和 Y 的數量

這一段是整題最核心的地方。

對每個一般位置 (k,l)：

如果這格是 'X'，先給目前格子一個 1。 如果這格是 'Y'，先給 county[k][l] 一個 1。

然後套用二維 prefix sum 的公式：

prefix[i][j] = 上面 + 左邊 - 左上角重複部分 + 自己這格

所以這裡：

  • countx[k][l]
    • 表示 (0,0) ~ (k,l) 裡 'X' 的總數
  • county[k][l]
    • 表示 (0,0) ~ (k,l) 裡 'Y' 的總數

算完後就可以直接檢查這個前綴矩陣是不是合法答案。

6. 為什麼這樣數到的剛好就是題目要的子矩陣

因為題目要求子矩陣必須包含 grid[0][0]。

所以任一合法子矩陣的左上角一定只能是 (0,0)，不然就不可能包含這格。

也就是說，所有合法子矩陣其實都可以唯一表示成：

  • (0,0) 到 (i,j)

這正好就是 prefix sum 最適合處理的形式。

所以這份程式不是在枚舉所有子矩陣，而是在枚舉所有可能的右下角 (i,j)，再檢查對應的前綴矩陣是否符合條件。

7. 最後回傳答案

return ans;

當所有位置都處理完後，ans 就是符合條件的子矩陣總數。

⏱️ 複雜度

設 m = grid.length，n = grid[0].length。

  • 時間複雜度：O(mn)

    每個位置都只被處理一次。

  • 空間複雜度：O(mn)

    額外使用了兩個 m x n 的 prefix sum 矩陣 countx 和 county。

💻 程式碼實作

class Solution {
public:
    int numberOfSubmatrices(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> countx(m, vector<int>(n, 0)); // 前綴和計算X,Y數量
        vector<vector<int>> county(m, vector<int>(n, 0));
        if (grid[0][0] == 'X') {
            countx[0][0]++;
        } else if (grid[0][0] == 'Y') {
            county[0][0]++;
        }

        int ans = 0; // 一樣的次數
        for (int i = 1; i < m; i++) {
            if (grid[i][0] == 'X') {
                countx[i][0]++;
            } else if (grid[i][0] == 'Y') {
                county[i][0]++;
            }
            countx[i][0] += countx[i - 1][0];
            county[i][0] += county[i - 1][0];
            if (countx[i][0] - county[i][0] == 0 && countx[i][0] > 0) {
                ans++;
            }
        }
        for (int j = 1; j < n; j++) {
            if (grid[0][j] == 'X') {
                countx[0][j]++;
            } else if (grid[0][j] == 'Y') {
                county[0][j]++;
            }
            countx[0][j] += countx[0][j - 1];
            county[0][j] += county[0][j - 1];
            if (countx[0][j] - county[0][j] == 0 && countx[0][j] > 0) {
                ans++;
            }
        }
        for (int k = 1; k < m; k++) {
            for (int l = 1; l < n; l++) {
                if (grid[k][l] == 'X') {
                    countx[k][l]++;
                } else if (grid[k][l] == 'Y') {
                    county[k][l]++;
                }
                countx[k][l] += (countx[k - 1][l] + countx[k][l - 1]);
                countx[k][l] -= countx[k - 1][l - 1];
                county[k][l] += (county[k - 1][l] + county[k][l - 1]);
                county[k][l] -= county[k - 1][l - 1];
                if (countx[k][l] - county[k][l] == 0 && countx[k][l] > 0) {
                    ans++;
                }
            }
        }
        return ans;
    }
};

https://leetcode.com/problems/count-submatrices-with-equal-frequency-of-x-and-y/

文章資訊

作者：scottnick
撰寫日期：2026-03-19
類別： Array Matrix Prefix Sum Medium
原文連結：https://scottnick.github.io/cpp-notes/all%20problems/3212-count-submatrices-with-equal-frequency-of-x-and-y.html