TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Course  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2098
  • Problem
  • P2098【状态压缩DP】Toy Bricks
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

    Ray又在NPC问题了:这里有一个箱子,还有若干个玩具。
    我们可以假设玩具的数量是没有上限的。我们还知道这个箱子是不规则的,或者可以说,他的外形比较像一个矩形,但是内部却有很多突起,这些突起很可恶,他可以一直突到玩具的顶盖部。为了简化这个NPC问题,Ray只保留了一种形状的玩具

    Ray想知道对于一个给定的箱子,最多可以放下多少个这样的玩具。

    Input Format

    第一行两个用空格隔开的整数n 和m表示玩具箱的长度和宽度
    第二行到第n+1行,每行m个用空格隔开的字符“#”“.”;“#”表示这里是一个障碍物。“.”表示这里可以放东西。

    Output Format

    一行一个整数表示最多的玩具个数

    Sample Input

    5 4
    #.#.
    ...#
    #..#
    #...
    ##.#

    Sample Output

    2

    Hint

    0<=n<=100

    0<=m<=10


    Source  HZOI