题目链接

题意概述:给出由0 1构成的矩阵,求没有0 1 相邻的最大子矩阵的最大子正方形。

解题思路:设f[i][j]表示i j向上能到哪,l[i][j] r[i][j]表示向左/右,转移时分开计算矩形和正方形即可。

#include<cstring>
#include<iostream>
#include<cctype>
#include<cstdio>
#include<algorithm>
using namespace std;
inline int read()
{
register int X=;register char ch=;bool flag=;
for(;!isdigit(ch);ch=getchar()) if(ch=='-') flag=;
for(;isdigit(ch);ch=getchar()) X=(X<<)+(X<<)+ch-'';
return (flag ? -X : X);
}
inline void write(int x)
{
if(x>) write(x/);
putchar(x%+'');
}
const int N=;
int l[N][N],r[N][N],f[N][N],n,m,a[N][N],ans1=,ans2=;
int min(const int x,const int y){return (x < y ? x : y);}
int max(const int x,const int y){return (x < y ? y : x);}
int main()
{
n=read(),m=read();
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
a[i][j]=read(),l[i][j]=r[i][j]=(j== ? : j),f[i][j]=;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
if(a[i][j] != a[i][j-])
l[i][j]=l[i][j-];
for(int j=m-;j>=;j--)
if(a[i][j] != a[i][j+])
r[i][j]=r[i][j+];
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
if(i > && a[i][j] != a[i-][j])
l[i][j]=max(l[i][j],l[i-][j]),r[i][j]=min(r[i][j],r[i-][j]),f[i][j]=f[i-][j]+;
int k=r[i][j]-l[i][j]+,h=min(k,f[i][j]);
ans1=max(ans1,k*f[i][j]);
ans2=max(ans2,h*h);
}
write(ans2),putchar('\n'),write(ans1);
}

最新文章

  1. 项目开发之UML之初识
  2. hdu Virtual Friends
  3. android的 makefile里 的常用 宏定义
  4. 怎么给OCR文字识别软件设置正确的扫描分辨率
  5. .NET Framework4.0 下的多线程
  6. POJ -3050 Hopscotch
  7. HDOJ 1237题 简单计算器
  8. poj2287
  9. C# 2 闰年平年 老狼几点了
  10. Vmware linux 安装 Vmware Tools 提示只读
  11. Android Annotations Eclipse 配置 (3)
  12. PHP Switch 语句
  13. 关于win7+VS2017环境下的opencv-contirb配置的一个坑
  14. 在 Activity 中实现 getContentView 操作
  15. Centos 04 基础系统优化命令
  16. BZOJ4972 八月月赛 Problem B 小Q的方格纸 二维前缀和
  17. 安装ik分词器以及版本和ES版本的兼容性
  18. 吴裕雄 python 机器学习-KNN算法(1)
  19. 2.select查询用法
  20. Spring学习13-中IOC(工厂模式)和AOP(代理模式)的详细解释

热门文章

  1. mybatis关联映射一对一
  2. 27、获取图片验证需要的uuId
  3. 冬虫夏草winterwormsummerherb英语
  4. Win10下免安装版MySQL8.0.16的安装和配置
  5. 爬虫之selenium模块;无头浏览器的使用
  6. List加载因子和扩容因子
  7. Linux之ubuntu下载
  8. Office--CVE-2017-11882【远程代码执行】
  9. rootkit——一种特殊的恶意软件,它的功能是在安装目标上隐藏自身及指定的文件、进程和网络链接等信息,一般都和木马、后门等其他恶意程序结合使用
  10. Locust性能测试6-命令行参数详解