A15025 | Yin Yang
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
You are given a rectangular grid with $n$ rows and $m$ columns. $n$ and $m$ are divisible by $4$ . Some of the cells are already colored black or white. It is guaranteed that no two colored cells share a corner or an edge.
Color the remaining cells in a way that both the black and the white cells becomes orthogonally connected or determine that it is impossible.
Consider a graph, where the black cells are the nodes. Two nodes are adjacent if the corresponding cells share an edge. If the described graph is connected, the black cells are orthogonally connected. Same for white cells.
Color the remaining cells in a way that both the black and the white cells becomes orthogonally connected or determine that it is impossible.
Consider a graph, where the black cells are the nodes. Two nodes are adjacent if the corresponding cells share an edge. If the described graph is connected, the black cells are orthogonally connected. Same for white cells.
输入格式
The input consists of multiple test cases. The first line of the input contains a single integer $t$ ( $1 \le t \le 4000$ ) — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers $n$ , $m$ ( $8 \le n, m \le 500$ , $n$ and $m$ are divisible by $4$ ) — the number of rows and columns.
Each of the next $n$ lines contains $m$ characters. Each character is either 'B', 'W' or '.', representing black, white or empty cell respectively. Two colored (black or white) cell does not share a corner or an edge.
It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $250\,000$ .
The first line of each test case contains two integers $n$ , $m$ ( $8 \le n, m \le 500$ , $n$ and $m$ are divisible by $4$ ) — the number of rows and columns.
Each of the next $n$ lines contains $m$ characters. Each character is either 'B', 'W' or '.', representing black, white or empty cell respectively. Two colored (black or white) cell does not share a corner or an edge.
It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $250\,000$ .
输出格式
For each testcase print "NO" if there is no solution, otherwise print "YES" and a grid with the same format. If there are multiple solutions, you can print any.
输入输出样例
输入 #1
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
输出 #1
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
Solution for test case 1:
Test case 2: one can see that the black and the white part can't be connected in the same time. So the answer is "NO".
Test case 2: one can see that the black and the white part can't be connected in the same time. So the answer is "NO".
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted