Cave Paintings

题目描述

贝茜成为了一名艺术家，正在创作洞穴画！她当前的作品是一张高度为 $N$ 的网格，每一行恰好包含 $M$ 个方格（$1\le N,M\le 1000$）。每个方格要么是空的，要么被岩石填充，要么被水填充。贝茜已经画好了包含岩石的方格，包括整幅画的边界。现在她想把一些空方格填上水，使得如果这幅画是真实的，水将不会产生净运动。

定义从上往下第 $i$ 行的方格高度为 $N+1-i$。贝茜希望她的画满足如下约束： 假设方格 $a$ 被水填充。若存在一条从 $a$ 到方格 $b$ 的路径，路径只经过高度不高于 $a$ 的空方格或水方格，且路径上任意相邻两格共享一条边，则 $b$ 也必须被水填充。

求贝茜可以创作的不同画作数量，对 $10^9+7$ 取模。贝茜可以将任意数量的空方格填上水，包括一个也不填或全部填满。

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $M$。 接下来 $N$ 行每行包含 $M$ 个字符。每个字符为 '.' 或 '#', 分别表示空方格与被岩石填充的方格。 第一行与最后一行、第一列与最后一列只包含 '#'.

输出格式

输出一个整数：满足约束的画作数量对 $10^9+7$ 取模的结果。

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

9

提示

评分： 测试点 1-5 满足 $N,M\le 10.$ 测试点 6-15 没有额外限制。

如果第二行中的某个方格被水填充，那么所有空方格都必须被水填充。否则，假设第二行中没有这样的方格被水填充。此时贝茜可以选择填充第三行中三个在水平方向上连续的空方格区域的任意子集。因此，画作数量等于 $1+2^3=9.$

题目来源：Daniel Zhang

标签: USACO|2020|Platinum

来源

USACO|2020|Platinum