CF1368G Shifting Dominoes

Bill 喜欢玩多米诺骨牌。他拿了一个 $n \times m$ 的棋盘，将其划分为相等的方格，并用多米诺骨牌完全覆盖。每个多米诺骨牌覆盖棋盘上两个相邻的格子，可以是水平或垂直方向，每个格子恰好被一个多米诺骨牌的一半覆盖（即没有未被覆盖的格子，也没有两个多米诺骨牌覆盖同一个格子）。 之后，Bill 决定用覆盖好的棋盘玩一玩，并在社交媒体上分享一些照片。首先，他从棋盘上恰好移除一个多米诺骨牌，使得两个格子变为空。接着，他可以移动多米诺骨牌。每个多米诺骨牌只能沿着其长边方向移动。如果该方向上的下一个格子当前是空的，则可以进行移动。Bill 不想忘记原始的覆盖方式，因此他保证在任何时刻，每个多米诺骨牌都至少有一个格子与其原始位置重叠。 在移除一个多米诺骨牌并进行若干次（可能为零次）移动后，Bill 会给棋盘拍照并发布。由于使用了大量滤镜，照片上看不到多米诺骨牌的边界，只能识别出棋盘上两个空格的位置。发布照片后，Bill 会将棋盘恢复到原始状态，然后重新开始这个过程。 Bill 想要发布尽可能多的照片，但不会发布重复的照片。你能帮他计算他最多能发布多少张不同的照片吗？注意，只有当照片中两个空格的位置不同，照片才算不同。

第一行包含两个正整数 $n$ 和 $m$（$nm \leq 2 \times 10^5$），分别表示棋盘的高度和宽度。 接下来的 $n$ 行描述了棋盘的覆盖方式，从上到下按行给出。每行包含 $m$ 个字符，表示该行从左到右的每个格子。每个字符是 U、D、L 或 R，分别表示该格子被多米诺骨牌的上半部分、下半部分、左半部分或右半部分覆盖。 保证给定的覆盖方式是合法的，即每个半多米诺骨牌在相应位置都有对应的另一半。特别地，由于可以覆盖，棋盘上的格子数是偶数。

输出一个整数，表示 Bill 最多能拍摄多少张不同的照片。

在第一个样例中，移除任意一个多米诺骨牌后都无法进行移动，因此一共可以拍摄四张不同的照片。 在第二个样例中，移除最左边的多米诺骨牌后，可以通过独立地移动/不移动其余两个多米诺骨牌，共有四种照片。再移除右侧的某一个多米诺骨牌，可以获得另外两种不同的照片。 由 ChatGPT 4.1 翻译