11165: 矩形填充
[Creator : ]
Description
一个 $n\times m$ 的网格,由黑色与白色格子组成。
在一次操作中,你可以选择任意两个相同颜色的格子,以这两个格子为对角的子矩形中所有格子都改成与它俩相同颜色。
形式化地说,如果你选中的两个格子坐标为 $(x_1,y_1),(x_2,y_2)$,颜色都是 $c$,满足 $\text{min}(x_1,x_2)≤x≤\text{max}(x_1,x_2),\ \text{min}(y_1,y_2)≤y≤\text{may}(y_1,y_2)$ 的所有坐标 $(x,y)$ 对应的格子都被改成颜色 $c$。
下图展现了两次操作:
请问,是否能通过若干次上述操作(也可以为 $0$ 次),将整个网格变成同一种颜色?你需要回答 $t$ 组询问。
Input
第一行为一个整数 $t$;
接下来为 $t$ 组询问,每组询问的组成如下:
第一行为两个整数 $n,m$;
接下来有 $n$ 行,每行 $m$ 个字符,$s_{ij}$ 表示第 $i$ 行第 $j$ 列的格子,为 W
表示白色,为 B
表示黑色。
Output
$t$ 行,第 $i$ 为对第 $i$ 组询问的回答,如果能做到,输出
YES
,否则输出 NO
。 Constraints
$1 \leq t \leq 10^4$
$1 \leq n,m \leq 500$
题目保证所有的 $n \cdot m$ 之和不超过 $3 \cdot 10^5$。
$1 \leq n,m \leq 500$
题目保证所有的 $n \cdot m$ 之和不超过 $3 \cdot 10^5$。
Sample 1 Input
3
6 6
WWWWBW
WBWWWW
BBBWWW
BWWWBB
WWBWBB
BBBWBW
4 5
BBBBB
BBBBB
WWWWW
WWWWW
4 4
WWBW
BBWB
WWBB
BBBB
Sample 1 Output
YES
NO
YES