2025 ICPC Asia Manila Regional（2025 ICPC 亚洲菲律宾马尼拉）——F. Map and Fold（折纸题）

题目大意

题目大意

有一张地图，可以通过若干次贯穿整张纸的水平方向和垂直方向的折叠，最终被折叠成一个 $1 \times 1$ 的正方形单位。每次折叠都发生在距离纸张边缘为整数个单位的位置。

当把这张地图重新完全展开时，所有的折痕会把纸张划分成一个 $r \times c$ 的正方形网格。任意两个相邻正方形之间共享的边即为一条长度为 $1$ 的折痕。根据折叠方向的不同，折痕可以分为两种：

题目给定一个 $(2r - 1) \times (2c - 1)$ 的字符矩阵，用来编码展开后的地图折痕状态。矩阵中第 $i$ 行第 $j$ 列的字符含义如下：

任务：给定上述字符矩阵，判断是否能通过上述合法的折叠过程（每次水平或垂直折叠贯穿当前的整张纸，直到折成 $1 \times 1$ 大小），在现实中精准复现该矩阵所描述的折痕图案。如果可以，输出 YES，否则输出 NO。

样例及解释

样例输入

2
3 4
.V.V.M.
M+M+M+M
.M.M.V.
V+M+V+M
.M.M.V.
2 2
.M.
M+M
.M.

样例输出

1
2

YES
NO

样例解释
输入包含两个测试用例：

第一个测试用例给出了一个 $(2 \times 3 - 1) \times (2 \times 4 - 1)$ 即 $5 \times 7$ 的字符矩阵，代表一个 $3 \times 4$ 的网格。该图案是可以通过规定的折叠方法真实得到的折痕分布，因此输出 YES。
第二个测试用例给出了一个 $3 \times 3$ 的字符矩阵，代表一个 $2 \times 2$ 的网格。其四周的折痕全为 M（峰折），而在这种必须贯穿整张纸面进行折叠的规则下，无法在现实中构造出这样的折痕组合，因此输出 NO。