TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P6557
  • 题目
  • P6557【USACO 2020 Jan Platinum】Cave Paintings
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,512m
    问题描述

    Bessie 成为了一名艺术家,正在创作壁画!她现在正在创作的作品是一个高为 \(N\) 的方阵,方阵的每行都由 \(M\) 个方格组成($1\le N,M\le 1000$)。每个方格是空的,画了石头,或者画了水。Bessie 已经画上了包含石头的方格,包括整幅画作的边界。她现在想要将某些空的方格画上水,使得如果这幅画是真实的,其中应当不存在水的净移动。定义从上到下第 \(i\) 行的方格的高度为 \(N+1-i\)。Bessie 想要她的画作满足以下限制:

    假设方格 $a$ 画的是水。那么如果存在一条从 $a$ 到方格 $b$ 的路径,由高度不超过 $a$ 的空的方格或是有水的方格组成,路径中每相邻两个方格都有一条公共边,那么 $b$ 画的也是水。

    求 Bessie 可以创作的不同作品的数量模 $10^9+7$ 的余数。Bessie 可以将任意数量的空格画上水,包括不画以及全画。

    输入格式

    输入格式(文件名:cave.in):

    输入的第一行包含两个空格分隔的整数 $N$ 和 $M$。

    以下 $N$ 行每行包含 $M$ 个字符。每个字符均为 '.' 或 '#',分别表示一个空的方格和一个画有石头的方格。第一行和最后一行、第一列和最后一列仅包含 '#'。

    输出格式

    输出格式(文件名:cave.out):

    输出一个整数,为满足限制的作品的数量模 $10^9+7$ 的余数。
    样例输入 1

    4 9
    #########
    #...#...#
    #.#...#.#
    #########

    样例输出 1

    9

    样例输入 2

    10 10
    ##########
    #.##...###
    #.#.#..###
    #.#.....##
    #......#.#
    #..###.#.#
    #####..###
    ##...###.#
    #####..#.#
    ##########

    样例输出 2

    360

    提示

    测试点性质:

    • 测试点 1-5 满足 $N,M\le 10$。
    • 测试点 6-15 没有额外限制。
    样例解释:

    如果第二行中的任意一个方格被画上水,那么所有空的方格必须都被画上水。否则,假设没有这样的方格画有水。那么 Bessie 可以选择画上第三行的空格组成的三个连续区域的任意子集。所以,画作的总数等于 $1+2^3=9$。