AT_abc311_f [ABC311F] Yet Another Grid Task

题目描述

有一个 $N \times M$ 的网格。
我们用 $(i, j)$ 表示从上到下第 $i$ 行、从左到右第 $j$ 列的格子。
每个格子要么是白色，要么是黑色，这些信息通过 $N$ 个长度为 $M$ 的字符串 $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+1, j)$ 存在，则格子 $(i+1, j)$ 也必须是黑色。
  • 如果格子 $(i, j)$ 是黑色，且格子 $(i+1, j+1)$ 存在，则格子 $(i+1, j+1)$ 也必须是黑色。

高桥可以将任意数量（包括 $0$ 个）的白色格子涂成黑色，以此来让网格变得美丽。
请你求出高桥能制作的不同美丽网格的种类数，结果对 $998244353$ 取模。
注意，如果存在至少一个格子的颜色不同，则认为两个网格是不同的。

输入格式

输入通过标准输入按以下格式给出。

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

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

输入输出样例 #1

输入 #1

2 2
.#
..

输出 #1

3

输入输出样例 #2

输入 #2

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

输出 #2

92

输入输出样例 #3

输入 #3

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

输出 #3

604936632

说明/提示

限制条件

• $1 \le N, M \le 2000$
• $S_i$ 是仅由 . 和 # 组成的长度为 $M$ 的字符串

样例解释 1

可以制作的美丽网格有如下 $3$ 种：

.#
.#
##

.#
##
##

##
##
##

样例解释 3

请对 $998244353$ 取模后输出答案。

由 ChatGPT 4.1 翻译