cpp题目描述给第一个01矩阵现在你需要在其中圈一个矩形出来要求是：这个矩形四个顶角都是1矩形的长和宽都至少是2。请问有多少种方法？输入格式第一行一个整数 �n表示一个 �×�n×n 的矩阵。接下来 �n 行每行 �n 个数字为 00 或者 11。输出格式输出可以有多少种方案画出矩形使得矩形四个顶角都是 11。输入输出样例样例 1输入样例 复制40101001101111111输出样例 复制7数据

解题思路： 首先遍历整个矩阵，找到所有为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)