leetcode第221题（最大正方形）的本地IDE实现
leetcode第221题（最大正方形）的本地IDE实现
问题描述：
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。PS：本文也对只包含0的最大正方形面积进行了运算
示例:
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(){
vector<string>v;
string s;
int row;
cin>>row;
//int i=0;
for(int i=0;i<row;i++){
cin>>s;
v.push_back(s);
}
int col=s.size();
//int dp[row][col];
/*求‘1’正方形的最大面积*/
vector<vector<int>> dp(row, vector<int>(col, 0));//多维向量的声明和初始化
// vector<vector<int>>dp(row);//另外一种多维向量声明和初始化方法
// for(int i=0;i<row;i++)
// dp[i].resize(col);
int res = 0;
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (i == 0 || j == 0) { //初始化第一行、第一列
dp[i][j] = v[i][j] – ‘0’;
}
else if (v[i][j] == ‘1’) {//动态规划
dp[i][j] = min(dp[i – 1][j – 1], min(dp[i][j – 1], dp[i – 1][j])) + 1;
}
res =max(res, dp[i][j]);
}
}
cout<< res*res<<endl;
/*求‘0’正方形的最大面积*/
vector<vector<int>> dd(row, vector<int>(col, 0));
int ans=0l;
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (i == 0 || j == 0) { //初始化第一行、第一列
while(v[i][j]==‘0’){
dd[i][j] = v[i][j] – ‘0’+1;
break;
}
while (v[i][j]==‘1’){
dd[i][j]=v[i][j]-‘1’;
break;
}
}
else if (v[i][j] == ‘0’) {
dd[i][j] = min(dd[i – 1][j – 1], min(dd[i][j – 1], dd[i – 1][j])) + 1;
}
ans=max(ans, dd[i][j]);
}
}
cout<<ans*ans<<endl;
cout<<max(ans*ans,res*res)<<endl;
}
收获：
1.vector<string>v可以写成类似二维数组的形式 即v[i][j]代表一个字符
2.多维向量的声明及初始化line27:vector<vector<int>>dp(row,vector<int>(col,0))
或者vector<vector<int>>dp(row);for(int i=0;i<row;i++) dp[i].resize(col);
3.动态规划的知识