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

描述:

晓萌有一个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 条评论
登录 后参与评论

相关文章

来自专栏tkokof 的技术,小趣及杂念

随便聊聊水面效果的2D实现(二)

之前提到想要随便聊一聊RippleEffect的2D实现方法,近来又总算有了些许空余时间,于是便有了这篇东西~

1923
来自专栏搞前端的李蚊子

Html5模拟通讯录人员排序(sen.js)

// JavaScript Document  var PY_Json_Str = ""; var PY_Str_1 = ""; var PY_Str_...

6426
来自专栏Hadoop数据仓库

Oracle sqlldr 如何导入一个日期列

1. LOAD DATA INFILE * INTO TABLE test FIELDS TERMINATED BY X'9' TRAILING NULLCO...

1876
来自专栏专知

2018年SCI期刊最新影响因子排行,最高244,人工智能TPAMI9.455

2018年6月26日,最新的SCI影响因子正式发布,涵盖1万2千篇期刊。CA-Cancer J Clin 依然拔得头筹,其影响因子今年再创新高,达244.585...

1482
来自专栏linux驱动个人学习

高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分,其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

1K4
来自专栏码匠的流水账

聊聊HystrixThreadPool

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/HystrixThreadPool.java

931
来自专栏Java学习123

HTTP Status 500 - {msg=SolrCore 'collection1' is not available due to init failure: Could not load c

45311
来自专栏PPV课数据科学社区

【学习】七天搞定SAS(三):基本模块调用

搞定基本的函数之后,开始鼓捣SAS里面的模型。也就是说,要开始写PROC了。说实话,越学SAS,越觉得SAS像Stata...无论是从输出的样式,还是语法。好不...

3025
来自专栏菩提树下的杨过

linq to sql取出随机记录/多表查询/将查询出的结果生成xml

在手写sql的年代,如果想从sqlserver数据库随机取几条数据,可以利用order by NewId()轻松实现,要实现多表查询也可以用select * f...

2236
来自专栏余生开发

echarts太阳分布图-饼图来回穿梭

var dom = document.getElementById("container");

1442

扫码关注云+社区