| Codeforces Round 941 (Div. 2) |
|---|
| Закончено |
Дана таблица $$$n \times m$$$ из белых и черных клеток. За одну операцию можно выбрать две клетки одного цвета и покрасить в этот цвет все клетки в подпрямоугольнике между ними.
Формально, если выбрать позиции $$$(x_1, y_1)$$$ и $$$(x_2, y_2)$$$, которые в данный момент имеют цвет $$$c$$$, установите цвет всех $$$(x, y)$$$, где $$$\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\cdot 10^5$$$.
Для каждого теста выведите «YES», если возможно сделать все клетки в таблице одного цвета, и «NO» в противном случае.
Вы можете выводить ответ в любом регистре (верхний или нижний). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
82 1WB6 6WWWWBWWBWWWWBBBWWWBWWWBBWWBWBBBBBWBW1 1W2 2BBBB3 4BWBWWBWBBWBW4 2BBBBWWWW4 4WWBWBBWBWWBBBBBB1 5WBBWB
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$$$ в белый цвет. После этих двух операций все клетки будут белыми.
