CF1966B.Rectangle Filling

普及-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个 $n \times m$ 的网格，每个格子是白色或黑色。每次操作，你可以选择任意两个颜色相同的格子，并将它们之间的子矩形内所有格子都染成该颜色。

具体来说，如果你选择了位置 $(x_1, y_1)$ 和 $(x_2, y_2)$ ，且它们当前颜色都是 $c$ ，那么你将所有满足 $\min(x_1, x_2) \le x \le \max(x_1, x_2)$ 且 $\min(y_1, y_2) \le y \le \max(y_1, y_2)$ 的格子颜色都设置为 $c$ 。

下图展示了在一个网格上可能进行的两步操作：

请判断，经过任意次操作（也可以不操作），是否有可能让网格内所有格子的颜色都相同。

输入格式

输入的第一行包含一个整数 $t$ （ $1 \le t \le 10^4$ ），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ （ $1 \le n, m \le 500$ ），分别表示网格的行数和列数。

接下来的 $n$ 行，每行包含 $m$ 个字符，字符为 'W' 或 'B'，表示网格初始时每个格子的颜色。

保证所有测试用例中 $n \cdot m$ 的总和不超过 $3 \times 10^5$ 。

输出格式

对于每个测试用例，如果可以让所有格子的颜色都相同，输出 "YES"；否则输出 "NO"。

你可以用任意大小写输出答案。例如，"yEs"、"yes"、"Yes" 和 "YES" 都会被识别为肯定回答。

输入输出样例

输入#1

8
2 1
W
B
6 6
WWWWBW
WBWWWW
BBBWWW
BWWWBB
WWBWBB
BBBWBW
1 1
W
2 2
BB
BB
3 4
BWBW
WBWB
BWBW
4 2
BB
BB
WW
WW
4 4
WWBW
BBWB
WWBB
BBBB
1 5
WBBWB

输出#1

NO
YES
YES
YES
YES
NO
YES
NO

说明/提示

在第一个样例中，无法通过任何操作改变任意格子的颜色，所以输出 NO。

第二个样例就是上图所示的情况。正如图中所示，通过两步操作可以让所有格子变为白色，所以输出 YES。

第三和第四个样例中，所有格子本来就已经是同一种颜色，所以输出 YES。

第五个样例中，可以通过两步操作完成。首先，选择位置 $(2, 1)$ 和 $(1, 4)$ ，将 $1 \le x \le 2$ 且 $1 \le y \le 4$ 的所有格子染成白色。然后，选择 $(2, 1)$ 和 $(3, 4)$ ，将 $2 \le x \le 3$ 且 $1 \le y \le 4$ 的所有格子染成白色。经过这两步操作后，所有格子都变成了白色。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页