| Codeforces Round 783 (Div. 1) |
|---|
| Закончено |
Дана прямоугольная сетка, состоящая из $$$n$$$ строк и $$$m$$$ столбцов. $$$n$$$ и $$$m$$$ делятся на $$$4$$$. Некоторые клетки уже покрашены в черный или белый. Гарантируется, что никакие две покрашенные клетки не являются соседями по стороне или углу.
Покрасьте оставшиеся клетки таким образом, чтобы и черные, и белые клетки стали ортогонально связными, или определите, что это невозможно.
Рассмотрим граф, в котором вершины — черные клетки. Две вершины соединены ребром, если соответствующие черные клетки являются соседями по стороне. Если получившийся граф связен, черные клетки считаются ортогонально связными. Аналогично для белых клеток.
Каждый тест состоит из нескольких наборов входных данных. Первая строка ввода содержит одно целое число $$$t$$$ ($$$1 \le t \le 4000$$$) — количество наборов входных данных. Далее следует их описание.
Первая строка каждого набора содержит два целых числа $$$n$$$, $$$m$$$ ($$$8 \le n, m \le 500$$$, $$$n$$$ и $$$m$$$ делятся на $$$4$$$) — количество строк и столбцов.
Каждая из следующих $$$n$$$ строк содержит $$$m$$$ символов. Каждый символ — 'B', 'W' или '.' — кодирует черную, белую или пустую клетку соответственно. Никакие две покрашенные (черные или белые) клетки не являются соседями по стороне или углу.
Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превосходит $$$250\,000$$$.
Для каждого набора входных данных выведите «NO», если решения не существует. В ином случае выведите «YES» и сетку в том же формате. Если существует несколько решений, выведите любое.
4 8 8 .W.W.... .....B.W .W.W.... .....W.W B.B..... ....B.B. B.W..... ....B.B. 8 8 B.W..B.W ........ W.B..W.B ........ ........ B.W..B.W ........ W.B..W.B 8 12 W.B......... ....B...B.W. B.B......... ....B...B.B. .B.......... ........B... .W..B.B...W. ............ 16 16 .W............W. ...W..W..W.W.... .B...........B.W ....W....W...... W......B....W.W. ..W.......B..... ....W...W....B.W .W....W....W.... ...B...........W W.....W...W..B.. ..W.W...W......B ............W... .W.B...B.B....B. .....W.....W.... ..W......W...W.. W...W..W...W...W
YES BWWWWWWW BWBBBBBW BWBWWWBW BWBWBWBW BWBWBWBW BWBBBWBW BWWWWWBW BBBBBBBW NO YES WWBBBBBBBBBB BWWWBBBBBBWB BBBWBBBWWWWB BBBWBBBWBBBB BBBWBBBWBBBB BBBWWWWWBBBB BWWWBBBWWWWB BBBBBBBBBBBB YES WWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWW WBBBBBBBBBBBBBWW WBBBWBWWWWBWWBWW WBBWWBBBWWBWWBWW WBWWWBWWWWBWWBWW WBBWWBBBWWBWWBWW WWBWWWWWWWWWWWWW WWBBBBBBBBBBBBWW WBBBWWWBWWWBWBWW WWWBWBBBWBBBWBBB WWWBWBWWWWWBWWBW WWWBWBBBWBBBWWBW WWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWW
Решение для первого набора входных данных:
Второй набор: можно показать, что черная и белая части не могут быть соединены одновременно. Таким образом, ответ «NO»
