动态规划-数正方形(详解)

描述:

晓萌有一个N×N的的棋盘,中间有N*N个正方形的1×1的格子,他随机在棋盘上撒上一些棋子(假设全部正好落在各个格子里)。他希望知道,当前的棋盘上有多少个不包含棋子的,由至少四个1×1的格子组成的正方形(正方形之间可以有重叠的部分)。

输入第1行为棋盘的边长N,第2行-第N+1组成一个每行有N个数字的棋盘,其中数字0表示这个格子内有棋子,1表示这个格子内没有棋子。(2≤N≤250)

输出包括多行,每行包括两个用空格分隔的数字,分别表示可以找到的正方形的边长和这种边长的正方形的个数。

样例输入

6
101111
001111
111111
001111
101101
111001

样例输出

2 10         //2*2的正方形有10个
3 4          //3*3的正方形有4个
4 1         //4*4的正方形有1个

分析:

显然这是个动态规划,若用暴力搜索,会在大数组上超时,所以需要每次保存上次的状态

先来分析下2*2的正方形,如下图:

从上图可以看出,当在第s[i][j]数组上,且这个数组值为1(有棋子),那它会与之前地s[i-1][j-1]、s[i-1][j]、s[i][j-1]有关,若这3个任意一个都不满足(为0)的话,那么s[i][j]就只能是个1*1正方形

再来深入分析,3*3的正方形,如下图:

 从上图可以看出,要想第s[i][j]数组上构成一个大于等于3*3的正方形,必须s[i-1][j-1]、s[i-1][j]、s[i][j-1]都至少是个2*2的正方形,比如上图(3,3), 不然就会像上图(2,2)那样

从这里我们可以看出s[i][j]非0情况下, 会等于 这3个数组(s[i-1][j-1]、s[i-1][j]、s[i][j-1])的最小值+1

最后再分析一个有0数组,就迎刃而解了:

同样地对于一个n*n正方形(n>=2),必定满足(n-1)*(n-1)正方形、(n-2)*(n-2)正方形 ... ...

 代码如下:

#include<stdio.h>
int s[300][300]={0},tp[300]={0};
int main()
{
    int i,j,n,min=0,m=1,cnt;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    scanf("%1d",&s[i][j]);
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    {
        if(s[i][j]!=0)   //第s[i][j]数组上,且这个数组值为1(有棋子)
        {
        min=(s[i-1][j]>s[i-1][j-1])?s[i-1][j-1]:s[i-1][j];
        min=(s[i][j-1]>min)?min:s[i][j-1];
        s[i][j]=min+1;               //等于 这3个数组(s[i-1][j-1]、s[i-1][j]、s[i][j-1])的最小值+1
        for(cnt=2;cnt<=min+1;cnt++) //对于一个n*n正方形(n>=2),必定满足(n-1)*(n-1)正方形、(n-2)*(n-2)正方形 ... ...
        tp[cnt]++;
        }            
    }
    for(i=2;i<=n;i++)
    if(tp[i]!=0)
    {   
    if(m)
    {
     printf("%d %d",i,tp[i]);
     m=0;
    }
    else   
    printf("\n%d %d",i,tp[i]);
    }
    return 0;
} 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我杨某人的青春满是悔恨

函数式思维

自从大四看了三章《SICP》之后我就自诩为一个函数式编程爱好者,之前也在公司分享过一个 Haskell 的 Topic,效果非常糟糕,讲到后来已经没剩几个人了,...

141
来自专栏带你撸出一手好代码

lambda表达式杂谈

上面的数据存放着一组人员姓名、年龄、性别相关的信息。 现在有一个需求, 获得年龄20岁以上,性别为女的人的姓名。 看到需求后, 很多人脑袋中产生的解决方案可能是...

3144
来自专栏武军超python专栏

2018年8月26日python标准(内建)模块,内建函数,元类

今天学到的新单词: sequence n数列,序列 reference n参考,v引用 variable adj变化的可变的 meta n元

1324
来自专栏趣谈编程

归并排序

面试官: 聊聊归并排序 归并排序是建立在归并操作的一种高效的排序方法,该方法采用了分治的思想,比较适用于处理较大规模的数据,但比较耗内存,今天我们聊聊归并排序 ...

4037
来自专栏数据结构与算法

洛谷P4136 谁能赢呢?

题目描述 小明和小红经常玩一个博弈游戏。给定一个n×n的棋盘,一个石头被放在棋盘的左上角。他们轮流移动石头。每一回合,选手只能把石头向上,下,左,右四个方向移动...

2546
来自专栏Java爬坑系列

【JAVA零基础入门系列】Day3 Java基本数据类型

  前两篇已经将开发环境搭建完成,如果你已经按之前的教程按部就班的完成了部署,那么世界上最优秀的编程语言之一和世界上最优秀的IDE之一已经出现在你的电脑上(此处...

1798
来自专栏编程微刊

2018年各大互联网前端面试题二(滴滴打车)

2702
来自专栏JackieZheng

Java8-初识Lambda

廉颇老矣,尚能饭否 Java,这位已经20多岁的编程语言,称得上是编程语言界的老大哥了。他曾经攻城略地,碾压各路编程语言小弟,风光无限,不可一世。现在,也是家大...

1847
来自专栏小樱的经验随笔

【Java学习笔记之二十二】解析接口在Java继承中的用法及实例分析

一、定义 Java接口(Interface),是一系列方法的声明,是一些方法特征的集合,一个接口只有方法的特征没有方法的实现,因此这些方法可以在不同的地方被不...

3135
来自专栏coding for love

JS进阶系列01-JS的弱类型和动态类型

首先,我们要弄清楚编程语言的两组划分,即弱类型和强类型,动态类型和静态类型。下面有一幅图,非常详细地说明了它们各自的定义和区别。

863

扫码关注云+社区