力扣221.最大正方形（动态规划）-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣221.最大正方形（动态规划）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

思路：

思路：从[0,0]元素开始，计算每个元素对应其与[0,0]之间矩阵块中最大正方形边长
情况：1）matrix [ i , j ] = ‘0’ --> 元素对应的最大正方形为0。
情况：2）matrix [ i , j ] = ‘1’ --> max ( matrix [ i-1 , j ] , matrix [ i - 1 , j - 1 ) ,matrix [ i , j - 1 ] ) + 1
具体实现：1）先找出第一行和第一列的最大正方形边长（只有1、0两种结果）；2）计算中间部分的每个元素对应最大正方形边长；3）找出所有元素对应正方形边长中最大值，计算面积；

/**
 * @author Limg
 * @date 2022/08/10
 * 在一个由 '0' 和 '1' 组成的二维矩阵内，
 * 找到只包含 '1' 的最大正方形，并返回其面积。
*/
#include<iostream>
#include<vector>
using namespace std;
int maximalSquare(vector<vector<char>>& matrix);
int main()
{
    //输入矩阵，便于测试
    int m=0,n=0;
    cin>>m;
    cin>>n;
    vector<vector<char> > matrix;
    char value;
    vector<char> temp;  
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>value;
            temp.push_back(value);
        }
        matrix.push_back(temp);
        temp.clear();
    }
    //调用函数
    cout<<maximalSquare(matrix)<<endl;
    return 0;
}
//解题函数
int maximalSquare(vector<vector<char>>& matrix) 
{
    int m = matrix.size();
    int n = matrix[0].size();
    int record[m][n];
    int max_curr = 0;  //计算最大边长
    for(int i=0;i<m;i++)  //第一列最大1，最小0
    {
        record[i][0] = int(matrix[i][0]-'0');
        max_curr = max(record[i][0],max_curr);
    }
    for(int j=0;j<n;j++)  //第一行最大1，最小0
    {
        record[0][j] = int(matrix[0][j]-'0');
        max_curr = max(record[0][j],max_curr);
    }
    for(int i=1;i<m;i++)  //中间部分依次计算
    {
        for(int j=1;j<n;j++)
        {
            if(matrix[i][j]-'0'==0)
            {
                record[i][j] = 0;
            }
            else
            {
                int min_2 = min(record[i-1][j-1],record[i-1][j]);
                record[i][j] = min(min_2,record[i][j-1])+1;
                max_curr = max(record[i][j],max_curr);
            } 
        }
    }
    return max_curr*max_curr;
}