Yet Another Grid Task

题目描述

有一个 $N \times M$ 的格子，玩家站在其上。
记 $(i,j)$ 为该格子从上数第 $i$ 行、从左数第 $j$ 列的格子。
该格子的每个格子是黑色或白色，用长度为 $M$ 的 $N$ 个字符串 $S_1,S_2,\dots,S_N$ 表示如下：

如果 $S_i$ 的第 $j$ 个字符是 $.$，则格子 $(i,j)$ 是白色； 如果 $S_i$ 的第 $j$ 个字符是 #，则格子 $(i,j)$ 是黑色。

当满足以下条件时，称该格子为 漂亮。

对于所有满足 $1 \le i \le N, 1 \le j \le M$ 的整数对 $(i,j)$，如果格子 $(i,j)$ 是黑色，则位于 $(i,j)$ 下面的格子以及位于 $(i,j)$ 的右下方相邻的格子也必须是黑色（若这些格子存在）。 形式上，以下所有条件都成立。 如果格子 $(i,j)$ 是黑色且格子 $(i+1,j)$ 存在，则格子 $(i+1,j)$ 也必须是黑色。 如果格子 $(i,j)$ 是黑色且格子 $(i+1,j+1)$ 存在，则格子 $(i+1,j+1)$ 也必须是黑色。

Takahashi 可以将零个或多个白色格子涂成黑色，他会这样做以使格子变为漂亮。
求他可以得到的不同漂亮格子的数量，对 $998244353$ 取模。
当存在某个格子在两种格子中颜色不同，则认为这两种格子不同。

输入格式

输入从标准输入给出，格式如下： $N$ $M$ $S_1$ $S_2$ $\vdots$ $S_N$

输出格式

输出一个整数，表示答案。

2 2
.#
..

3

.#  .#  ##
.#  ##  ##

5 5
....#
...#.
..#..
.#.#.
#...#

92

25 25
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................

604936632

提示

$1 \le N,M \le 2000$ $S_i$ 是由 $.$ 和 # 组成的长度为 $M$ 的字符串。他可以得到以下三种不同的漂亮格子：
对 $998244353$ 取模后的计数。

标签: AtCoder|abc311F

来源

AtCoder|abc311F