3339. [USACO20 Jan Platinum]Cave Paintings

【题目描述】

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 可以将任意数量的空格画上水，包括不画以及全画。

【输入格式】

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

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

【输出格式】

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

【样例输入】

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

【样例输出】

9

【样例解释】

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

【提示】

对于$ 33\% $的测试数据(测试点$ 1\sim5 $)，满足$ N,M ≤ 10 $。

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 一月公开赛 Platinum 组