洛谷 P1387 最大正方形 刷题笔记

P1387 最大正方形 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

找出一个 由数字1组成的最大正方形

输出该正方形的边长 ；

思路? dp

画图模拟?

可以发现 当 当前点a[i][j]=1,满足构成正方形的初步条件

而当前点能构成的最大正方形长度 由它的左上角 左边和上边正方形边长的最小值决定

最小值+1 即该点能构成的正方形

#include <iostream>
#include <cstdio>
using namespace std;
int a[101][101],n,m,f[101][101],ans;
int main()
{
? ? scanf("%d%d",&n,&m);//读入
? ? for (int i=1;i<=n;++i)
? ? ? ? for (int j=1;j<=m;++j)
? ? ? ? {
? ? ? ? ? ? scanf("%d",&a[i][j]);
? ? ? ? ? ? //因为只需用到i，j上方，左方，左上方的信息，读入同步处理
? ? ? ? ? ? if (a[i][j]==1) f[i][j]=min(f[i][j-1],f[i-1][j],f[i-1][j-1])+1;
? ? ? ? ? ? ans=max(ans,f[i][j]);//同步更新答案
? ? ? ? }
? ? printf("%d",ans);
return 0;
}

方法2

暴力枚举 每个点a[i][j]为左上角能构成的最大正方形

思路 来自 大佬??个人中心 - 洛谷

读入矩阵后?

倒着从最大边长开始枚举

从当前点开始逐行逐个检查 一旦找到为0的点就退出

如果检查完都符合 记录该边长值?

#include <bits/stdc++.h>
#define re register int
using namespace std;
bool f[202][202]={0},p;
int n,m,i,j,k,x,y,ans=0;
int main()
{
? int n,m;
?? ?cin>>n>>m;
?? ?for(int i=1;i<=n;i++){
?? ??? ?for(int j=1;j<=m;j++){
?? ??? ??? ?cin>>f[i][j];
?? ??? ??? ?
?? ??? ?}
?? ?} ? ? ? ? ?
? for (re i=1; i<=n; i++)
? ? for (re j=1; j<=m; j++)
? ? ? for (re k=min(n,m); k>ans; k--)//倒着枚举边长?
? ? ? ? {
? ? ? ? ? p=1;
? ? ? ? ? for (re x=i; x<i+k; x++) ? //逐个判断
? ? ? ? ? ? {
? ? ? ? ? ? ? for (re y=j; y<j+k; y++)
? ? ? ? ? ? ? ? if (!f[x][y]) ? ? ? ?//不是1的话
? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? p=0; break; ? ? ?//标记，跳出循环
? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? if (!p) break; ? ? ? ? //不符合没必要接着做
? ? ? ? ? ? }
? ? ? ? ? if (p) ? ? ? ? ? ? ? ? ? ? //检查完符合条件的话
? ? ? ? ? ? {
? ? ? ? ? ? ? ans=k; break; ? ? ? ? ?//记录可行边长最大值
?? ??? ??? ? ? ? ? ? ? ? ? ? ? ? ? ? //下次找到时候 如果小于该值就不做了?
? ? ? ? ? ? }
? ? ? ? }
? printf("%d",ans); ? ? ? ? ? ? ? ? ?
? return 0;
}
?