算法刷题：p1387 最大正方形

本文主要是介绍算法刷题：p1387 最大正方形，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

解题思路：

利用动态规划的思想设置一个标记数组flag[][]，flag[i][j]用来记录矩阵op[][]中以op[i][j]为右下角的子矩阵中最大的正方形边长，那么动态方程就是 flag[i][j]=min(flag[i-1][j],min(flag[i-1][j-1],flag[i][j-1]))+1;左侧和上方以及左上方中最小值+1

#include<bits/stdc++.h>
using namespace std;
int op[109][109];
int flag[109][109];
int main(void){int n,m;int ans=0;int i,j;cin>>n>>m;for(i=1;i<=n;i++){for(j=1;j<=m;j++){cin>>op[i][j];if(op[i][j]==1){flag[i][j]=min(flag[i-1][j],min(flag[i-1][j-1],flag[i][j-1]))+1;ans=max(ans,flag[i][j]);}}}   cout<<ans;return 0;
}

这篇关于算法刷题：p1387 最大正方形的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---