C++ 01 矩阵矩形计数问题

C++ 01 矩阵矩形计数问题

题目描述

给第一个01矩阵，现在你需要在其中圈一个矩形出来，要求是：这个矩形四个顶角都是1，矩形的长和宽都至少是2。请问有多少种方法？

输入格式

第一行一个整数 n，表示一个 n×n 的矩阵。

接下来 n 行，每行 n 个数字，为 0 或者 1。

输出格式

输出可以有多少种方案画出矩形，使得矩形四个顶角都是 1。

输入输出样例

样例 1

输入样例

4
0101
0011
0111
1111

输出样例

7

数据范围与提示

对于 50% 的数据： n 的范围 [1, 100];

对于 100% 的数据： n 的范围 [1, 300];

解题思路：

首先遍历整个矩阵，找到所有为1的位置，将其坐标保存下来。

然后遍历保存的坐标，对于每个坐标(x, y)，假设其为矩形的左上角顶点，然后往右边和下边扩展，找到合适的右下角顶点，计算出当前矩形的面积。

具体实现如下：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> matrix(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < n; j++) {
            matrix[i][j] = s[j] - '0';
        }
    }

    vector<pair<int, int>> ones; // 保存所有为1的位置
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 1) {
                ones.push_back(make_pair(i, j));
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < ones.size(); i++) {
        int x1 = ones[i].first;
        int y1 = ones[i].second;
        for (int j = i + 1; j < ones.size(); j++) {
            int x2 = ones[j].first;
            int y2 = ones[j].second;
            if (x2 < x1 || y2 < y1) {
                continue;
            }
            int area = (x2 - x1 + 1) * (y2 - y1 + 1);
            ans += area;
        }
    }

    cout << ans << endl;

    return 0;
}

复杂度分析：

遍历整个矩阵需要O(n^2)的时间复杂度，保存所有为1的位置需要O(n^2)的空间复杂度。然后遍历保存的坐标需要O(n^2)的时间复杂度。所以总的时间复杂度为O(n^2)，空间复杂度为O(n^2)。