P1681 最大正方形II

    • 613通过
    • 1.5K提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 高性能
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    忙完了学校的事,v神终于可以做他的“正事”:陪女朋友散步。一天,他和女朋友走着走着,不知不觉就来到了一个千里无烟的地方。v神正要往回走,如发现了一块牌子,牌子上有有一行小字和一张图,小字说道:“找到图上最大的交错正方形之后和我联系,这块地就是你的了。”在房价疯长的年代,v神当然不愿错过这个机会,于是开始找了起来……以v神的能力当然找不出来了,你能帮v神找出来吗?

    题目描述

    图上有一个矩阵,由N*M个格子组成,这些格子由两种颜色构成,黑色和白色。请找到面积最大的且内部是黑白交错(即两个相连的正方形颜色不能相同)的正方形。

    输入输出格式

    输入格式:

    第一行两个整数N和M,分别表示行数和列数。接下来有N行,每行M个数,0或1分别表示这个格子是黑色或白色。

    输出格式:

    仅有一行,表示满足条件最大正方形的 边长

    输入输出样例

    输入样例#1: 复制
    3 3
    0 1 0
    1 0 0
    1 1 1
    
    输出样例#1: 复制
    2

    说明

    样例解释:

    (1,1)到(2,2)这个正方形是满足条件的,它的边长是2

    数据范围约定:

    对于30%的数据,N <= 20

    对于60%的数据,N <=300

    对于100%的数据,N <= 1500

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。