美团2024年春招第一场笔试【技术】第一题：小美的平衡矩阵

题目：

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

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

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

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

输入描述：

第一行输入一个正整数，代表矩阵大小。接下来的行，每行输入一个长度为的 01 串，用来表示矩阵。

输出描述：

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

示例1

输入例子：

4
1010
0101
1100
0011

输出例子：

0
7
0
1

此题可以通过移动某一大小的窗格框来完成，从左向右，从上往下移动框，每次移动后计算框的和，最后得出此大小的框对应的答案。问题是该如何优化代码，尽量减少计算次数，这里采用预计算方式。

我们设定一个横宽为n(输入中的第一行数字)，纵高为m(目前规定的框大小)的临时辅助总和数组框，这个数组分别记录此框中每一列的总和，在我们移动计算此行的框的和时，我们只需加上框外右侧第一列的和，减去框中左侧第一列的和即可得到此框向右移动一列后的框的和。而我们真正需要访问源矩阵的时机仅仅只是每次重设框大小时需要的数组框初始化，以及计算下一行，也就是将框下移一行时所需的数组框同步下移更新而已，这样，我们的计算量大幅减小。

同时我们还可以注意到奇数框大小时完美矩阵数始终为0，因为奇数*奇数还是等于奇数，而奇数个二进制数当然不能凑出完美矩阵。另外，还有一种思路是不利用辅助框，直接让框蛇形移动，但这种移动方式将会为编程带来级的难度提升和性的调试复杂度，肠♂瘦。

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

int main()
{
    int n;
    int m, i, j, i1, j1; //分别代表目前所选框的边长、目前框的左上角元素的2个下标、某个框内的某个元素的2个下标
    int sum, count; //某一个框的和值(1为1,0为-1)，某种大小的框有多少个完美矩形
    string s;
    cin >> n;
    bool **arr = new bool *[n];
    int *tempsumarr = new int[n]; //临时的宽n高m的框中的每一列的和值，可以加快框的遍历移动速度
    for (i = 0; i < n; i++) { //申请并读入二维数组，注意输入二进制是连续的，不能直接按数字读入
        arr[i] = new bool[n];
        cin >> s;
        for (j = 0; j < n; j++) {
            if (s[j] == '1') {
                arr[i][j] = true;
            }
            else {
                arr[i][j] = false;
            }
        }
    }

    for (m = 1; m <= n; m++) { //遍历所有大小的框，计算其完美矩形
        if (m%2) { //奇数边长的框不可能完美
            cout << 0 << endl;
            continue;
        }
        //初始化当前边长框所需的值，需要初始化此框对应的tempsumarr
        count = 0;
        memset(tempsumarr, 0, n*sizeof(int));
        for (i1 = 0; i1 < m; i1++) { //横长为n纵为m
            for (j1 = 0; j1 < n; j1++) {
                if (arr[i1][j1]) {
                    tempsumarr[j1]++;
                }
                else {
                    tempsumarr[j1]--;
                }
            }
        }
        //从左上角第一个框开始，从左往右移动到最右，而后回到下一排的左侧重复进行直到右下角。注意移动框时i和j的值为移动前框的下标，而非移动后的框
        for (i = -1; i < n-m; i++) {
            //初始时刻tempsumarr不能移动，要先遍历第一排，而后再移动到下一排进行完整遍历，所以此处跳过第一次排移动
            if (i != -1) {
                for (j = 0; j < n; j++) {
                    tempsumarr[j] += 2*(arr[i+m][j]-arr[i][j]); //巧妙的更新sum
                }
            }
            //先初始化一个当前排的框并判定其是否完美
            sum = 0;
            for (j = 0; j < m; j++) {
                sum += tempsumarr[j];
            }
            if (!sum) {
                count++;
            }
            //而后再向右移动遍历所有框并判定
            for (j = 0; j < n-m; j++) {
                sum += tempsumarr[j+m]-tempsumarr[j];
                if (!sum) {
                    count++;
                }
            }
        }
        cout << count << endl;
    }
}