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

描述:

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

相关文章

来自专栏利炳根的专栏

学习笔记CB014:TensorFlow seq2seq模型步步进阶

神经网络。《Make Your Own Neural Network》,用非常通俗易懂描述讲解人工神经网络原理用代码实现,试验效果非常好。

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

LOJ #108. 多项式乘法

内存限制:256 MiB时间限制:1000 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: 匿名 提交提交记录统计讨论测试数据 题目描述 这是一道...

3258
来自专栏人工智能LeadAI

机器学习实战 | 第二章:线性回归模型

线性回归(Linear Regression) 这个类是传统最小二乘回归的类.是最基础的线性回归的类. class sklearn.linear_model....

3017
来自专栏程序员叨叨叨

8.4 CG 标准函数库

和 C 的标准函数库类似,Cg 提供了一系列内建的标准函数。这些函数用于执行数学上的通用计算或通用算法(纹理映射等),例如,需要求取入射光线的反射光线方向向量可...

925
来自专栏潇涧技术专栏

Python Algorithms - C3 Counting 101

原书主要介绍了一些基础数学,例如排列组合以及递归循环等,但是本节只重点介绍计算算法的运行时间的三种方法

604
来自专栏ATYUN订阅号

利用统计方法,辨别和处理数据中的异常值

在建模时,清理数据样本非常重要,这样做可以确保观察结果充分代表问题。有时,数据集可能包含超出预期范围之外的极端值。这通常被称为异常值,通过理解甚至去除这些异常值...

963
来自专栏达摩兵的技术空间

牛博士的是不是‘4’数列

小易有一个长度为N的正整数数列A = {A[1], A[2], A[3]…, A[N]}。 牛博士给小易出了一个难题: 对数列A进行重新排列,使数列A满足所有的...

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

NDArray自动求导

NDArray可以很方便的求解导数,比如下面的例子:(代码主要参考自https://zh.gluon.ai/chapter_crashcourse/autogr...

18210
来自专栏人工智能LeadAI

使用TensorFlow实现手写识别(Softmax)

准备工作 由于将TensorFlow安装到了Conda的tensorflow环境,虽然可以用Jupyter notebook打开,但是没有提示,写代码不方便,所...

3585
来自专栏人工智能

十五:多层感知机与布尔函数

今天没有别的话,好好学习,多多转发! 本期内容是 【多层感知机与布尔函数】 场景描述 神经网络概念的诞生很大程度上受到了神经科学的启发。生物学研究表明,大脑皮层...

2128

扫码关注云+社区