思路:
- 思路:从[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;
}