CF1368G.Shifting Dominoes

Bill likes to play with dominoes. He took an $n \times m$ board divided into equal square cells, and covered it with dominoes. Each domino covers two adjacent cells of the board either horizontally or vertically, and each cell is covered exactly once with a half of one domino (that is, there are no uncovered cells, and no two dominoes cover the same cell twice).

After that Bill decided to play with the covered board and share some photos of it on social media. First, he removes exactly one domino from the board, freeing two of the cells. Next, he moves dominoes around. A domino can only be moved along the line parallel to its longer side. A move in the chosen direction is possible if the next cell in this direction is currently free. Bill doesn't want to lose track of what the original tiling looks like, so he makes sure that at any point each domino shares at least one cell with its original position.

After removing a domino and making several (possibly, zero) moves Bill takes a photo of the board and posts it. However, with the amount of filters Bill is using, domino borders are not visible, so only the two free cells of the board can be identified. When the photo is posted, Bill reverts the board to its original state and starts the process again.

Bill wants to post as many photos as possible, but he will not post any photo twice. How many distinct photos can he take? Recall that photos are different if the pairs of free cells in the photos are different.

比尔喜欢玩多米诺骨牌。他取了一块被划分为若干相同正方形格子的 $n \times m$ 棋盘，并用多米诺骨牌将其完全覆盖。每个多米诺骨牌恰好覆盖棋盘上两个相邻的格子（水平或垂直方向），且每个格子恰好被一个骨牌的一半所覆盖（即：没有未被覆盖的格子，也没有任何格子被两个骨牌重复覆盖）。

随后，比尔决定与这块已被覆盖的棋盘互动，并将一些照片分享到社交媒体上。首先，他从棋盘上恰好移除一个多米诺骨牌，从而腾出两个格子。接着，他移动其余的多米诺骨牌。一个多米诺骨牌只能沿着与其长边平行的方向移动；若在选定方向上的下一个格子当前为空，则该移动是可行的。比尔不想丢失对原始铺砌状态的记忆，因此他确保在任意时刻，每个骨牌都至少与它在原始位置上占据的一个格子重合。

在移除一个骨牌并进行若干次（可能为零次）移动之后，比尔为当前棋盘状态拍摄一张照片并发布。然而，由于比尔使用的滤镜效果太强，照片中多米诺骨牌的边界不可见，因此仅能识别出棋盘上那两个空着的格子。照片发布后，比尔会将棋盘恢复至原始铺砌状态，并重新开始这一过程。

比尔希望尽可能多地发布照片，但不会发布任何重复的照片。他最多能发布多少张互不相同的照片？注意：两张照片不同，当且仅当它们所对应的两个空格子组成的无序格子对不同。

The first line contains two positive integers $n$ and $m$ ($nm \leq 2 \cdot 10^5$) — height and width of the board respectively.

The next $n$ lines describe the tiling of the board, row by row from top to bottom. Each of these lines contains $m$ characters, describing the cells in the corresponding row left to right. Each character is one of U, D, L, or R, meaning that the cell is covered with a top, bottom, left, or right half of a domino respectively.

It is guaranteed that the described tiling is valid, that is, each half-domino has a counterpart in the relevant location. In particular, since tiling is possible, the number of cells in the board is even.

第一行包含两个正整数 $n$ 和 $m$（满足 $nm \leq 2 \cdot 10^5$），分别表示棋盘的高和宽。

接下来的 $n$ 行按从上到下的顺序描述棋盘的铺砌。每行包含 $m$ 个字符，表示对应行中从左到右的各个格子。每个字符为 U、D、L 或 R 中的一个，分别表示该格子被一个骨牌的上半部分、下半部分、左半部分或右半部分所覆盖。

保证所描述的铺砌是合法的，即每个半骨牌在相应位置均有其配对的另一半。特别地，由于铺砌可行，棋盘中的格子总数为偶数。

Print a single integer — the number of distinct photos Bill can take.

输出一个整数——Bill 可以拍摄的不同照片的数量。

In the first sample case, no moves are possible after removing any domino, thus there are four distinct photos.

In the second sample case, four photos are possible after removing the leftmost domino by independently moving/not moving the remaining two dominoes. Two more different photos are obtained by removing one of the dominoes on the right.

在第一个样例中，移除任意一个骨牌后均无法进行任何移动，因此共有四张不同的照片。

在第二个样例中，移除最左侧的骨牌后，剩余两个骨牌可各自独立选择移动或不移动，从而得到四张不同的照片；而移除右侧两个骨牌中的任意一个，则可额外得到两张不同的照片。