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

描述:

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

相关文章

来自专栏码匠的流水账

聊聊Color中的alpha值

color对象里头的alpha其实是指不透明度,其值范围为0-255,越大越不透明。 其通常对应opacity,这个就是单词语义表达的不透明度,其值范围[0,1...

982
来自专栏Golang语言社区

Golang语言实现猜数字小游戏的方法

随机生成一个数字,输入一个数字看是否匹对,匹配则结速,反之提示是大了还是小了 package main import ( "bufio" "f...

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

Flash/Flex学习笔记(22):滤镜学习

Silverlight中称之为“效果(Effect)”的东东,在Flash里叫“滤镜(Filter)",而且Flash里内置的滤镜要比Silverlight丰富...

2279
来自专栏Golang语言社区

Go语言实现猜数字小游戏的方法

package main import ( "bufio" "fmt" "math/rand" "os" "strconv" ...

3185
来自专栏听雨堂

EXCEL单元格的引用方式

EXCEL单元格的引用包括相对引用、绝对引用和混合引用三种。 相对引用   公式中的相对单元格引用(例如 A1)是基于包含公式和单元格引用的单元格的相对...

1897
来自专栏程序员同行者

JavaScript中的CSS属性对照表

1044
来自专栏LIN_ZONE

已知两点的经度和纬度,计算两点间的距离(php,javascript)

php代码:转载  http://www.cnblogs.com/caichenghui/p/5977431.html

971
来自专栏GreenLeaves

JavaScript之Style属性学习

当CSS使用伪类开始侵入DOM和JavaSCript所控制着的行为层时,DOM和JavaScript也使用他们的一系列样式去控制表现层,这篇随笔主要说的就是利用...

2198
来自专栏前端知识分享

第59天:缓动动画封装函数

比如说  console.log(Math.ceil(1.01))       结果 是 2  

973
来自专栏HTML5学堂

一个setInterval的小问题

一个setInterval的小问题 HTML5学堂:在制作页面动画效果中,很多情况都会用到定时器,setInterval则是计时器的一种,可按照指定的周期,不停...

3589

扫码关注云+社区

领取腾讯云代金券