- 好习惯,务必数组要初始化,因为中途不是按照顺序走的,他是跳着走的,这样的话,int数组又是随机初始化(也可能随机初始化一个很小的值,所以,务必使用vector且全部初始化0. 后续在做自己的开始初始化,以及计算值)
class Solution {
public:
/**
* 最大正方形
* @param matrix char字符型vector<vector<>>
* @return int整型
*/
int solve(vector<vector<char> >& matrix) {
// write code here
vector<vector<int>> dp(matrix.size(),vector<int>(matrix[0].size(),0));
// 初始化 dp 矩阵的第一列
for(int i = 0; i< matrix.size();i++){
// 如果当前点为 1 ,那么最大正方形就是他本身,最大边长也就是 1
dp[i][0] = matrix[i][0] - '0';
}
// 初始化 dp 矩阵的第一行
for(int i = 0; i< matrix[0].size();i++){
// 如果当前点为 1 ,那么最大正方形就是他本身,最大边长也就是 1
dp[0][i] = matrix[0][i] - '0';
}
int max_ =0;
// 遍历所有点,填充 dp 矩阵的所有位置。
for(int i = 1; i< matrix.size(); i++){
for(int j = 1; j< matrix[0].size();j++){
if(matrix[i][j] == '1'){//剪枝操作了。就导致部分dp没有初始化好,有垃圾数据。
dp[i][j]=min(dp[i-1][j-1],dp[i-1][j]);
dp[i][j]=min(dp[i][j],dp[i][j-1])+1;
max_=max(max_,dp[i][j]);
}
}
}
return max_*max_;
}
};