题目描述

在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形,输出边长。

输入输出格式

输入格式:

输入文件第一行为两个整数n,m(1<=n,m<=100),接下来n行,每行m个数字,用空格隔开,0或1.

输出格式:

一个整数,最大正方形的边长

输入输出样例

输入样例#1:

4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1
输出样例#1:

2

暴力A了(有技巧的暴力)
/*
二维前缀和枚举
这样的水题搞了一个多小时,原来是公式背错了......
枚举每一个子矩阵的和是否等于边长的平方 自己yy的,没想到还过了
不算慢。
但其实是dp......又伤心了
*/ #include<iostream>
#include<cstdio>
#define maxn 101 using namespace std;
int n,m,ans,tot,cnt;
int s[maxn][maxn],map[maxn][maxn],sum[maxn][maxn]; int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&map[i][j]);
s[i][j]=s[i][j-]+map[i][j];
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
sum[i][j]=sum[i-][j]+s[i][j]; for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
int p=i,q=j,tmp=;
if(map[p][q]== && sum[p][q]-sum[i-][q]-sum[p][j-]+sum[i-][j-]==tmp*tmp && p<=n&&q<=m)
{
while(map[p][q]== && sum[p][q]-sum[i-][q]-sum[p][j-]+sum[i-][j-]==tmp*tmp && p<=n&&q<=m)
p++,q++,tmp++;
ans=max(ans,p-i);
}
}
printf("%d\n",ans);
return ;
}

正解dp

//其实方程很好想,就是没勇气写,怕给输出0.... 

#include<iostream>
#include<cstdio> using namespace std;
int a[][]= {{}},f[][]= {{}},n,m,maxb=; int minn(int a,int b,int c)
{
return min(min(a,b),c);
} int main()
{
cin>>n>>m;
for(int i=; i<=n; i++)
for(int j=; j<=m; j++)
cin>>a[i][j];
for(int i=; i<=n; i++)
for(int j=; j<=m; j++)
{
if(a[i][j]==) continue;
f[i][j]=minn(f[i-][j],f[i][j-],f[i-][j-])+;
}
for(int i=; i<=n; i++)
for(int j=; j<=m; j++)
if(f[i][j]>maxb)
maxb=f[i][j];
cout<<maxb;
}

最新文章

  1. 第15章 LinkedList类(暂无)
  2. AH00098 pid file overwritten
  3. Java字节流:BufferedInputStream BufferedOutputStream
  4. TFS(Team Foundation Server)敏捷使用教程(四):工作项跟踪(1)
  5. STL之list容器用法
  6. java中对浮点数精度的处理DecimalFormat
  7. 轻量级操作系统FreeRTOS的内存管理机制(一)
  8. if(){}使用
  9. C++回顾day02---&lt;继承相关问题&gt;
  10. 1(3)IO流------字符流
  11. 基于jQuery消息提示框插件Tipso
  12. 使用 JavaScript, HTML 和 CSS 构建跨平台的桌面应用
  13. React.js 入门与实战课程思维导图
  14. MySQL基本SQL语句之数据插入、删除数据和更新数据
  15. SpringMVC拦截器和@ResponseBody注解冲突
  16. css background url 路径
  17. 优化cocos2d/x程序的内存使用和程序大小
  18. 2018.07.28 uoj#164. 【清华集训2015】V(线段树)
  19. Android学习系列(16)--App列表之圆角ListView
  20. CentOS日常维护及常用脚本

热门文章

  1. 10JDBC、CURD、XML、XPath
  2. MyBatis 中 resultMap 详解
  3. Docker从入门到实践
  4. Liunx学习笔记(三) 文件权限
  5. spring 学习(二)
  6. Leetcode 95.不同的二叉搜索树II
  7. [K/3Cloud]K3Cloud的移动审批方面
  8. 建立DJANGO的自定义TAG
  9. php7.0升级到php7.1
  10. CentOS和Window互相远程桌面方法