← 返回题目列表

Codeforces · 1368/G

G. 移动多米诺骨牌

中文机器翻译题面 查看原题

比尔喜欢玩多米诺骨牌。他拿了一块 $$$n \times m$$$ 的木板,分成相等的正方形单元,并用多米诺骨牌覆盖它。每个多米诺骨牌水平或垂直覆盖棋盘上的两个相邻单元格,并且每个单元格恰好被一个多米诺骨牌的一半覆盖一次(即,没有未覆盖的单元格,并且没有两个多米诺骨牌两次覆盖同一个单元格)。

之后,比尔决定玩一下有盖的木板,并在社交媒体上分享一些它的照片。首先,他从板上移除了一张多米诺骨牌,释放了其中的两个单元。接下来,他移动多米诺骨牌。多米诺骨牌只能沿着与其长边平行的线移动。如果该方向上的下一个单元当前空闲,则可以沿所选方向移动。 Bill 不想忘记原始平铺的样子,因此他确保在任何时候,每个多米诺骨牌都至少与其原始位置共享一个单元格。

移除多米诺骨牌并进行几次(可能是零次)移动后,比尔拍摄了多米诺骨牌的照片并将其发布。然而,随着比尔使用的过滤器数量的增加,多米诺骨牌边框是不可见的,因此只能识别板上的两个空闲单元。照片发布后,比尔将板恢复到原始状态并再次开始该过程。

Bill 希望发布尽可能多的照片,但他不会将任何照片发布两次。他能拍多少张不同的照片?回想一下,如果照片中的空闲单元对不同,则照片也会不同。

输入

第一行包含两个正整数 $$$n$$$ 和 $$$m$$$ ($$$nm \leq 2 \cdot 10^5$$$) — 分别是棋盘的高度和宽度。

接下来的 $$$n$$$ 行描述了板的平铺,从上到下逐行。每行都包含 $$$m$$$ 字符,从左到右描述相应行中的单元格。每个字符都是 U、D、L 或 R 之一,这意味着单元格分别被多米诺骨牌的上半部分、下半部分、左半部分或右半部分覆盖。

保证所描述的平铺是有效的,即每个半多米诺骨牌在相关位置都有对应的。特别是,由于可以平铺,因此板中的单元数量是偶数。

输出

打印一个整数——比尔可以拍摄的不同照片的数量。

示例

输入 #1

2 4
UUUU
DDDD

输出 #1

4

输入 #2

2 3
ULR
DLR

输出 #2

6

输入 #3

6 6
ULRUUU
DUUDDD
UDDLRU
DLRLRD
ULRULR
DLRDLR

输出 #3

133

注意

在第一个示例中,移除任何多米诺骨牌后就无法移动,因此有四张不同的照片。

在第二个示例案例中,通过独立移动/不移动剩余的两个多米诺骨牌来移除最左边的多米诺骨牌后,可以拍摄四张照片。通过移除右侧的多米诺骨牌之一,可以获得另外两张不同的照片。