跳到主要内容

小美的平衡矩阵

题目描述​

小美拿到了一个n∗n的矩阵，其中每个元素是 0 或者 1。

小美认为一个矩形区域是完美的，当且仅当该区域内 0 的数量恰好等于 1 的数量。

现在，小美希望你回答有多少个i∗i的完美矩形区域。你需要回答1≤i≤n的所有答案。

输入描述​

第一行输入一个正整数n，代表矩阵大小。

接下来的n行，每行输入一个长度为n的 01 串，用来表示矩阵。

输出描述​

输出n行，第i行输出i*i的完美矩形区域的数量。

示例​

输入：
4
1010
0101
1100
0011

输出：
0
7
0
1

解释：
- 1×1矩形：每个单元格只有一个元素，无法同时包含0和1，所以完美矩形数量为0
- 2×2矩形：需要包含2个0和2个1才是完美的，遍历所有可能的2×2区域：
  - (0,0)到(1,1)：1010/0101 → 包含2个0和2个1 ✓
  - (0,1)到(1,2)：0101/1010 → 包含2个0和2个1 ✓
  - (0,2)到(1,3)：1001/0110 → 包含2个0和2个1 ✓
  - (1,0)到(2,1)：0110/1100 → 包含2个0和2个1 ✓
  - (1,1)到(2,2)：1010/1000 → 包含2个0和2个1 ✓
  - (1,2)到(2,3)：0100/0011 → 包含2个0和2个1 ✓
  - (2,0)到(3,1)：1100/0011 → 包含2个0和2个1 ✓
  - (2,1)到(3,2)：1000/0011 → 包含1个0和3个1 ✗
  - (2,2)到(3,3)：0011/0011 → 包含2个0和2个1 ✗
  共7个完美的2×2矩形
- 3×3矩形：需要包含4.5个0和4.5个1，但元素数量必须是整数，所以不可能完美，数量为0
- 4×4矩形：整个矩阵包含8个0和8个1，是完美的，所以数量为1

解题思路​

核心观察：

  1. 完美矩形要求0和1的数量相等，即1的数量 = 矩形面积/2
  2. 奇数边长的矩形不可能是完美矩形（面积为奇数，无法平分）

前缀和优化（推荐）

预计算二维前缀和，快速求出任意子矩阵中1的数量

时间复杂度：O(n³)，空间复杂度：O(n²)

适用于大规模数据

C++ 解法​

// 使用前缀和技术
#include <iostream>
#include <vector>
#include <string>

int main()
{
    int n;
    std::cin >> n;

    // 读取二维矩阵
    std::vector<std::vector<int>> matrix(n, std::vector<int>(n));
    for (int i = 0; i < n; ++i) {
        std::string row;
        std::cin >> row;
        for (int j = 0; j < n; ++j) {
            matrix[i][j] = row[j] - '0';
        }
    }

    // 计算前缀和
    // 初始化前缀和矩阵
    // prefixSum[i][j]表示从(0,0)到(i-1,j-1)这个矩形区域中所有元素的和。
    std::vector<std::vector<int>> prefixSum(n + 1, std::vector<int>(n + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + matrix[i - 1][j - 1];
        }
    }

    // 对每种i*i大小的矩阵进行统计
    for (int i = 1; i <= n; ++i) {
        int count = 0;

        // 提前判断：i为奇数则跳过
        if (i % 2 == 1) {
            std::cout << 0 << std::endl;
            continue;
        }

        for (int r = 1; r <= n - i + 1; ++r) {
            for (int c = 1; c <= n - i + 1; ++c) {
                // 计算子矩阵中1的数量
                // 左上角位置(r,c) 和右下角位置(r+i-1,c+i-1)
                // 减去上方与左侧区域和，加上左上角区域和
                int onesCount = prefixSum[r + i - 1][c + i - 1] - prefixSum[r -1][c + i - 1] -
                                prefixSum[r + i - 1][c - 1] + prefixSum[r - 1][c - 1];
                // 检查是否为完美矩形
                if (onesCount == i * i / 2) {
                    count++;
                }
            }
        }
        std::cout << count << std::endl;
    }
    return 0;
}