第2题 漂亮网格 查看测评数据信息
n行m列的二维网格,每个格子要么是'.',要么是'#',其中'.'表示白色格子,'#'表示黑色格子。
从上往下,行的编号是1至n。从左往右,列的编号是从1至m。
网格被称为"漂亮网格",当且仅当同时满足如下的两个条件:
1、对于任意的1<=i<=n, 1<=j<=m, 如果格子(i,j)是黑色格子,若格子(i+1, j)存在,格子(i+1,j)必须也是黑色格子。
2、对于任意的1<=i<=n, 1<=j<=m, 如果格子(i,j)是黑色格子,若格子(i+1, j+1)存在,格子(i+1,j+1)必须也是黑色格子。
读入一个二维网格,你可以把其中的0个或者多个白色格子修改成黑色格子,以使得网格变成“漂亮网格”。
问总共可以有多少种不同的“漂亮网格”?
下面解释不同的“漂亮网格”,假如有"漂亮网格"A和"漂亮网格"B,
若存在某个格子(i,j),使得该格子在"漂亮网格"A和"漂亮网格"B的颜色是不一样的,
那么"漂亮网格"A和"漂亮网格"B就是不同的"漂亮网格"。
输入格式
第1行,n和m。 1<=n,m<=2000。
接下来是n行m列的二维网格。
输出格式
一个整数,答案模998244353。
输入/输出例子1
输入:
2 2
.#
..
输出:
3
输入/输出例子2
输入:
5 5
....#
...#.
..#..
.#.#.
#...#
输出:
92
输入/输出例子3
输入:
25 25
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
输出:
604936632
样例解释
无
作者:课程账号 更新时间:2023-09-23 17:25:57
以下是参考程序:标签:输出,格子,.........................,漂亮,网格,DP,输入 From: https://www.cnblogs.com/didiao233/p/18034192