#PU996. USACO 2020 January Contest, Platinum — Problem 1. Cave Paintings

    ID: 1534 传统题 文件IO:cave 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:jan20来源:usaco.orgscoring:equal_test_cases

USACO 2020 January Contest, Platinum — Problem 1. Cave Paintings

USACO 2020 January Contest, Platinum — Problem 1. Cave Paintings

题目描述

Bessie has become an artist and is creating paintings of caves! Her current work in progress is a grid of height NN such that each row of the grid contains exactly MM squares (1≤N,M≤10001\le N,M\le 1000). Each square is either empty, filled with rock, or filled with water. Bessie has already painted the squares containing rock, including the entire border of the painting. She now wants to fill some empty squares with water such that if the painting were real, there would be no net motion of water. Define the height of a square in the ii-th row from the top to be N+1−iN+1-i. Bessie wants her painting to satisfy the following constraint: Suppose that square aa is filled with water. Then if there exists a path from aa to square bb using only empty or water squares that are not higher than aa such that every two adjacent squares on the path share a side, then bb is also filled with water. Find the number of different paintings Bessie can make modulo 109+710^9+7. Bessie may fill any number of empty squares with water, including none or all.

输入格式

The first line contains two space-separated integers NN and MM. The next NN lines of input each contain MM characters. Each character is either '.' or '#', representing an empty square and a square filled with rock, respectively. The first and last row and first and last column only contain '#'.

输出格式

A single integer: the number of paintings satisfying the constraint modulo 109+710^9+7.

数据范围

Test cases 1-5 satisfy N,M≤10.N,M\le 10. Test cases 6-15 satisfy no additional constraints.

样例

样例 1

4 9
#########
#...#...#
#.#...#.#
#########
9
If a square in the second row is filled with water, then all empty squares must
be filled with water. Otherwise, assume that no such squares are filled with
water. Then Bessie can choose to fill any subset of the three horizontally
contiguous regions of empty squares in the third row. Thus, the number of
paintings is equal to $1+2^3=9.$
Problem credits: Daniel Zhang