首页 > 其他分享 >漂亮网格(DP)

漂亮网格(DP)

时间:2024-02-26 13:55:24浏览次数:20  
标签:输出 格子 ......................... 漂亮 网格 DP 输入

第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

image.png

以下是参考程序:

标签:输出,格子,.........................,漂亮,网格,DP,输入
From: https://www.cnblogs.com/didiao233/p/18034192

相关文章

  • Rockchip RK3399 - DRM edp驱动程序
    ----------------------------------------------------------------------------------------------------------------------------开发板:NanoPC-T4开发板eMMC:16GBLPDDR3:4GB显示屏:15.6英寸HDMI接口显示屏u-boot:2023.04linux:6.3----------------------------------......
  • Part3: Dive into DDPM
    背景整个系列有相对完整的公式推导,若正文中有涉及到的省略部分,皆额外整理在Part4,并会在正文中会指明具体位置。在Part2基于\(\text{VariationalInference}\),找到原目标函数\(-\ln{p_\theta(x_0)}\)的上界\(L\),定义如下:\[\begin{aligned}L:=&\mathbb{E}_q\left[-\log\frac......
  • AT_dp
    AT_dp本来是想提高一下DP,然后发现就只有几道蓝题有点启发性,紫题都是板题...x题目描述你有\(n\)个箱子,编号从\(1\)到\(n\),每个箱子有三个属性,以第\(i\)个箱子为例,分别是重量\(w_i\),承重能力\(s_i\),价值\(v_i\)。你想建一座塔,因此需要将一些箱子堆叠起来,但是每个箱子......
  • 动物园 (APIO 2007) 状压DP
    动物园\([APIO\2007]\)·题意:新建的圆形动物园是亚太地区的骄傲。圆形动物园坐落于太平洋的一个小岛上,包含一大圈围栏,每个围栏里有一种动物。如下图所示:你是动物园的公关主管。你要做的是,让每个参观动物园的游客都尽可能高兴。今天有一群小朋友来到动物园参观,你希望能让他......
  • 动物园(APIO 2007)(状压DP)
    动物园题解题目描述原题来自:APIO2007新建的圆形动物园是亚太地区的骄傲。圆形动物园坐落于太平洋的一个小岛上,包含一大圈围栏,每个围栏里有一种动物。如下图所示:你是动物园的公关主管。你要做的是,让每个参观动物园的游客都尽可能高兴。今天有一群小朋友来到动物园参观,你希望......
  • 基于STM32F407MAC与DP83848实现以太网通讯三(STM32F407MAC配置以及数据收发)
    本章实现了基于STM32F407MAC的数据收发功能,通过开发板的RJ45接口连接网线到电脑,电脑使用Wiershark工具抓包验证。参考文档:DP83848IV英文DP83848EP中文STM32F4xx参考手册一、工程模板以及参考源码的获取工程源码我使用的正点原子的探索者开发板STM32F407(V2)参考源码:正点原子......
  • WiMinet 评说1.3:模拟式UDP中继技术缺陷
        在《WiMinet评说1.2:多跳无线网络的现状》一文中,我们提到:在室外长距离的无线自组织网络中,由于节点之间的链路损耗较大,其链路预算相对不足,其包误码率PER会相应升高,也就是丢包概率p会比较大;而在一个大规模网络中,某些分支节点的通讯链路又会比较深,也就是网络跳数n比......
  • 长链剖分&DP
    长链剖分优化DP长链剖分有一些美妙的性质一个点跳到根最多经过\(\sqrtn\)条链向上跳链,链长一定会增加,最坏是\(1,2,3,...,\sqrtn\)所有长链的总链长相加为n(如说)优化DP如果dp中有一维和深度有关,就考虑优化,考虑用长儿子\(O(1)\)转移(一般是平移,考虑用指针),其他暴力转......
  • 数论分块性质优化DP状态
    6311.mobitel给定一个r行s列的矩阵,每个格子里都有一个正整数。问如果从左上角走到右下角,且每次只能向右或向下走到相邻格子,那么使得路径上所有数的乘积不小于n的路径有多少条?对于100%的数据,1<=r,s<=300,1<=n<=10^6,矩阵中的数不超过10^6。so,一个普通的思想就是设f[......
  • 单调栈优化DP
    当有形如\(f_i=min_{j=0}^{l(i)}f_j+w转移代价\)我们就可以使用单调栈优化DP为什么不用单调队列???当有形如\(f_i=min_{j=l(i)}^{i-1}f_j+w转移代价\)我们就可以使用单调队列优化DP至于为毛,就可以从它的工作原理上去分析6305.最小值\(dp_i=min_{j=0}^{i-1}g_j+f(min_{x=j+1......