C++ 01矩阵中矩形计数算法 - 详细解析与代码实现

C++ 01矩阵中矩形计数算法 - 详细解析与代码实现

题目描述

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

输入格式

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

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

输出格式

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

解题思路：

首先，我们需要遍历整个矩阵，找到每个顶角为 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 来存储矩阵的元素。