c++解决在一个二维01矩阵中找到全为1的最大正方形，返回其面积。

c++解决在一个二维01矩阵中找到全为1的最大正方形，返回其面积。 样例 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 返回4

该问题可以使用动态规划来解决。我们可以定义一个二维数组 dp，其中 dp[i][j] 表示以矩阵中第 i 行和第 j 列为右下角的正方形的最大边长。

动态规划的状态转移方程如下：

如果 matrix[i][j] 为 0，那么 dp[i][j] 必然为 0，因为以 matrix[i][j] 为右下角的正方形不存在。 如果 matrix[i][j] 为 1，那么 dp[i][j] 的值由其上方、左方和左上方的三个相邻位置的 dp 值决定。具体而言，dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。

遍历整个矩阵，更新 dp 数组的同时，记录最大边长。最终返回最大边长的平方即为最大正方形的面积。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int maximalSquare(vector<vector<int>>& matrix) {
    if (matrix.empty() || matrix[0].empty()) {
        return 0;
    }

    int m = matrix.size();
    int n = matrix[0].size();
    int maxSide = 0;

    vector<vector<int>> dp(m, vector<int>(n, 0));

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (matrix[i][j] == 1) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
                }

                maxSide = max(maxSide, dp[i][j]);
            }
        }
    }

    return maxSide * maxSide;
}

int main() {
    vector<vector<int>> matrix = {
        {1, 0, 1, 0, 0},
        {1, 1, 1, 1, 1},
        {1, 1, 1, 1, 1},
        {1, 0, 1, 0, 1},
        {1, 0, 1, 0, 0}
    };

    cout << maximalSquare(matrix) << endl;

    return 0;
}