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

解题思路： 我们可以遍历矩阵的每一个元素，以当前元素作为矩形的左上角，然后在该元素的右方和下方搜索矩形的右下角，判断该矩形是否满足要求。如果满足要求，计数器加一。最后输出计数器的值即可。

具体实现步骤如下：

1. 读取矩阵的大小n，并创建一个n×n的矩阵matrix来保存输入的矩阵。
2. 创建一个变量count，用于计数满足要求的矩形的个数。
3. 遍历矩阵的每一个元素，以当前元素作为矩形的左上角：
   • 在当前元素的右方和下方搜索矩形的右下角，判断该矩形是否满足要求。
   • 如果满足要求，计数器count加一。
4. 输出计数器count的值。

时间复杂度分析： 遍历矩阵的每一个元素需要O(n^2)的时间复杂度，判断矩形是否满足要求的时间复杂度是O(n)，所以总的时间复杂度是O(n^3)。

空间复杂度分析： 除了输入和输出的空间外，只需要O(1)的额外空间，所以空间复杂度是O(1)。

C++代码实现如下：

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int matrix[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j];
        }
    }

    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 1) {
                for (int k = i+1; k < n; k++) {
                    for (int l = j+1; l < n; l++) {
                        if (matrix[k][l] == 1 && matrix[i][l] == 1 && matrix[k][j] == 1) {
                            count++;
                        }
                    }
                }
            }
        }
    }

    cout << count << endl;
    return 0;
}

复杂度分析：

• 时间复杂度：O(n^3)
• 空间复杂度：O(1