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

解题思路： 首先，我们需要遍历整个矩阵，找到每个顶角为1的位置。

然后，对于每个顶角为1的位置，我们需要向右和向下扩展，直到遇到0为止。扩展的长度即为矩形的长和宽。

最后，我们将所有矩形的长和宽相乘，即可得到总的方案数。

算法步骤：

1. 读取输入的矩阵大小n和矩阵元素的值；
2. 初始化答案ans为0；
3. 遍历整个矩阵，找到每个顶角为1的位置；
4. 对于每个顶角为1的位置，向右和向下扩展，直到遇到0为止，记录扩展的长度；
5. 将所有矩形的长和宽相乘，累加到答案ans中；
6. 输出答案ans。

代码实现如下：

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

int main() {
    int n;
    cin >> n;
    vector<vector<int>> matrix(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j];
        }
    }
    
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 1) {
                int right = 1;
                int down = 1;
                while (j + right < n && matrix[i][j + right] == 1) {
                    right++;
                }
                while (i + down < n && matrix[i + down][j] == 1) {
                    down++;
                }
                ans += (right - 1) * (down - 1);
            }
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

复杂度分析：

• 时间复杂度：O(n^2)，其中n为矩阵的大小，需要遍历整个矩阵。
• 空间复杂度：O(n^2)，需要使用一个二维数组matrix来存储矩阵的元素