P1950 长方形_NOI导刊2009提高(2)

    • 105通过
    • 391提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp NOI导刊
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小明今天突发奇想,想从一张用过的纸中剪出一个长方形。

    为了简化问题,小明做出如下规定:

    (1)这张纸的长宽分别为n,m。小明讲这张纸看成是由n*m个格子组成,在剪的时候,只能沿着格子的边缘剪。

    (2)这张纸有些地方小明以前在上面画过,剪出来的长方形不能含有以前画过的地方。

    (3)剪出来的长方形的大小没有限制。

    小明看着这张纸,想了好多种剪的方法,可是到底有几种呢?小明数不过来,你能帮帮他吗?

    输入输出格式

    输入格式:

    第一行两个正整数n,m,表示这张纸的长度和宽度。

    接下来有n行,每行m个字符,每个字符为“*”或者“.”。

    字符“*”表示以前在这个格子上画过,字符“.”表示以前在这个格子上没画过。

    输出格式:

    仅一个整数,表示方案数。

    输入输出样例

    输入样例#1: 复制
    6 4
    ....
    .***
    .*..
    .***
    ...*
    .***
    输出样例#1: 复制
    38

    说明

    【数据规模】

    对10%的数据,满足1<=n<=10,1<=m<=10

    对30%的数据,满足1<=n<=50,1<=m<=50

    对100%的数据,满足1<=n<=1000,1<=m<=1000

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