#P12529. [XJTUPC 2025] 对称隔离:黑白之战

    ID: 14080 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 2 上传者: 标签>模拟2025Special JudgeO2优化高校校赛

[XJTUPC 2025] 对称隔离:黑白之战

题目描述

你在玩一款叫做「你的克拉夫特」的游戏。在这个游戏里,你可以在一个充满着方块的三维空间中自由地创造和破坏不同种类的方块。

现在你脚下有一块由 N×MN\times M 个格子组成的网格。一开始,你在这些格子上铺满了白色地毯,然后你就去睡觉了。

但是不幸的是,在你睡觉的时候,出题人将一些白色地毯偷偷换成了黑色地毯。

当你醒来再次打开游戏,你发现你的杰作被污染了,所以你非常气愤!所以你决定将错就错,希望通过保持现有黑色地毯不变,将部分白色地毯染黑,来满足下面两个条件:

  • 任意两个黑色地毯所在的格子不能共享公共边,即满足:
    • 若第 ii 行第 jj 列格子中为黑色地毯,则第 i1i-1 行第 jj 列、第 i+1i+1 行第 jj 列、第 ii 行第 j1j-1 列、第 ii 行第 j+1j+1 列格子中如果存在地毯,则不能为黑色地毯。
  • 最终形成的图案至少存在一条水平或者竖直的对称轴,即下面两个命题中至少满足一个:
    • 对于任意的 i[1,N]i \in [1,N]j[1,M]j \in [1,M],第 ii 行第 jj 列格子中的地毯颜色与第 Ni+1N-i+1 行第 jj 列格子中的地毯颜色相同;
    • 对于任意的 i[1,N]i \in [1,N]j[1,M]j \in [1,M],第 ii 行第 jj 列格子中的地毯颜色与第 ii 行第 Mj+1M-j+1 列格子中的地毯颜色相同。

你需要判断你是否可以达成这两个条件。

注意:你不能破坏已有的黑色地毯。

输入格式

第一行,两个整数 NNMM (1N,M1001\le N,M\le 100),用一个空格分隔,表示网格的大小。

接下来 NN 行,每行一个长度为 MM 的字符串 SSSS 中某一位为 W\tt{W} 表示这个位置是一块白色地毯,为 B\tt{B} 表示这个位置是一块黑色地毯。字符串中不会出现除此以外的字符。

输出格式

如果你可以达成题目中给出的条件,输出 Yes\tt{Yes};否则,输出 No\tt{No}

答案对大小写不敏感。例如 yEs\tt{yEs}, Yes\tt{Yes}, yes\tt{yes}YES\tt{YES} 都可以表示你可以达成条件。

4 4
WWWW
WBWW
WWWW
WWWW

No
4 4
BWWB
WWWW
WWWW
WWWB

Yes
4 4
BWWW
WBWW
WWBW
WWWW

No
5 5
BWBWB
WBWBW
BWBWB
WBWBW
BWBWB

Yes
2 2
BB
WW

No
2 2
WW
WW

Yes
8 6
WWBWWW
BWWWWW
WBWWWW
WWWWBW
BWWWWW
WWBWWW
WBWWWW
BWWWWW
No

提示

对于第一组样例:

最左边的图是你醒来时看到的情况,你无法通过把白色地毯换成黑色地毯以达成条件。中间和最右边的图,显示了两种可能的更换地毯的方式,但并不能满足题目中的两个要求(中间的图不存在水平或者竖直的对称轴;最右边的图黑色地毯共享公共边)。可以证明,任何更换地毯的方式均不符合要求,所以输出 No\tt{No}

对于第二组样例:

如图显示了一种合法的更换地毯的方式。你可以把左下角的白色地毯换成黑色地毯,这样符合题目中的两个要求。因此,你应该输出 Yes\tt{Yes}

对于第三组样例:

这是一种可能的更换地毯的方式,但是这个方式并不是合法的。请记住:只有存在水平或者竖直的对称轴才被视作合法的方案。

对于第四组样例:

你醒来的时候看到的情况本身已经是合法的了,所以你不需要进行操作。

对于第五组样例:你醒来的时候已经有两个共享公共边的黑色地毯了,所以你无法更换白色地毯以符合要求。

对于第六组样例:全是白色地毯的图案也被视作是合法的,因为它有水平或者竖直的对称轴,同时不存在两个共享公共边的黑色地毯。