Today we will be playing a red and white colouring game (no, this is not the Russian…
- User
Today we will be playing a red and white colouring game (no, this is not the Russian Civil War; these are just the colours of the Canadian flag).
You are given an n × m grid of "R", "W", and "." characters. "R" is red, "W" is white and "." is blank. The neighbours of a cell are those that share an edge with it (those that only share a corner do not count).
Your job is to colour the blank cells red or white so that every red cell only has white neighbours (and no red ones) and every white cell only has red neighbours (and no white ones). You are not allowed to recolour already coloured cells. Input
The first line contains t (1 ≤ t ≤ 100), the number of test cases.
In each test case, the first line will contain n (1 ≤ n ≤ 50) and m (1 ≤ m ≤ 50), the height and width of the grid respectively.
The next n lines will contain the grid. Each character of the grid is either 'R', 'W', or '.'.
Output
For each test case, output "YES" if there is a valid grid or "NO" if there is not.
If there is, output the grid on the next n lines. If there are multiple answers, print any.
In the output, the "YES"s and "NO"s are case-insensitive, meaning that outputs such as "yEs" and "nO" are valid. However, the grid is case-sensitive.
Example
Input
3 4 6 .R.... ...... ...... .W.... 4 4 .R.W .... .... .... 5 1 R W R W R
Output
YES WRWRWR RWRWRW WRWRWR RWRWRW NO YES R W R W R
Note
The answer for the first example case is given in the example output, and it can be proven that no grid exists that satisfies the requirements of the second example case. In the third example all cells are initially coloured, and the colouring is valid.
Assistant
We need to solve this problem: Given an n x m grid of characters 'R', 'W', '.'; we need to fill '.' with either 'R' or 'W' such that each colored cell (including pre-colored ones) satisfies: every neighbor (up, down, left, right) must be of opposite color. That is, no two adjacent cells can be the same color. Essentially, the grid must be a proper 2-coloring (bipartite) of the underlying graph (grid graph). The graph is bipartite because grid is bipartite (like chessboard). So the condition is that the coloring must be a proper 2-coloring where colors are R and W.
Given some pre-colored cells, we need to see if we can assign colors to remaining cells consistently. Since the grid graph is bipartite, it's always possible to assign colors if the pre-colored cells do not conflict: i.e., for any two pre-colored cells that are adjacent, they must be opposite colors; also, if we consider the parity (like chessboard coloring), all cells in one part of the bipartition must have the same color? Actually, in a bipartite graph, there are two partitions (like black and white squares of a chessboard). If we want a proper 2-coloring, we can assign one color to one partition and the opposite color to the other. However, we have two possible assignments: either partition 0 gets R and partition 1 gets W, or partition 0 gets W and partition 1 gets R. The pre-colored cells may force one assignment or the other, or conflict.
Thus the problem reduces to: The grid cells have coordinates (i,j). Their parity is (i+j) mod 2. Let's define two types: even parity and odd parity. In a proper 2-coloring, all even parity cells must have the same color, and all odd parity cells must have the opposite color. So the condition for existence: For any two pre-colored cells with same parity, they must have the same color; for any two with opposite parity, they must have opposite colors. Equivalently, there is a mapping from parity to color that satisfies all constraints. This mapping can be determined: If we set color for even parity to a variable C_even, then odd must be opposite. Check if any pre-colored cell contradicts this. Actually we can try both assignments: even=R, odd=W and even=W, odd=R. For each, check if it matches all pre-colored cells. If at least one works, we can fill accordingly (for '.' cells, assign based on the assignment). Output the grid.
Wait: There is a nuance: The grid might be disconnected? But the grid graph is connected for a rectangular grid? Actually if n,m >=1, the grid graph is connected if there is at least one cell and all cells are adjacent via edges. But even if it's disconnected (still bipartite). The above parity rule holds for each component? In a grid, all cells are connected? Actually consider n,m >=1, the grid graph (each cell connected to up/down/left/right) is connected as long as there is a path between any two cells. In a rectangular grid, it's always connected (since you can move horizontally and vertically). So there's one component. But even if there were multiple components (if the grid had obstacles? but there are none, all cells exist), it's connected. So parity works globally.
Thus solution:
For each test case: Read n,m and grid (list of strings). Initialize two possible assignments: Option 1: even = 'R', odd = 'W' Option 2: even = 'W', odd = 'R'
For each assignment, iterate over all cells (i,j) that are not '.'. For each such cell, compute parity = (i+j) % 2. Expected color = even if parity==0 else odd. If grid[i][j] != expected, then assignment invalid. If assignment passes all pre-colored cells, then it is valid. Choose first valid (or any). If none valid, output NO.
If valid, construct output grid: For each cell, if it's '.', assign based on parity and chosen assignment; otherwise keep original.
Output YES and the grid.
Check edge cases: n,m up to 50, t up to 100. Easy.
One nuance: The problem statement says: "every red cell only has white neighbours (and no red ones) and every white cell only has red neighbours (and no white ones)." That means a cell must have all neighbors opposite color. But what about cells that have no neighbors? That's fine. And also note that if a cell has a neighbor, that neighbor must be opposite color; so the condition is exactly that adjacent cells must have different colors. So it's exactly proper 2-coloring.
Thus solution seems trivial.
But wait: Could there be a situation where the grid is not fully connected? Still the parity approach works per connected component. However, in a grid with all cells present, it's connected. So fine.
Let's test with examples:
Example 1: 4x6 grid .R.... ...... ...... .W....
We'll compute parity (0-index or 1-index?). Usually i and j from 0 to n-1, m-1. Let's define (0,0) as top-left. Then for given R at (0,1) parity=1. W at (3,1) parity= (3+1)=4 mod2=0. So we have even parity cell? Actually (3,1) parity 4%2=0 even, color W. For assignment even=R odd=W: even expects R but we have W at even parity => conflict. For even=W odd=R: even expects W, odd expects R. At (0,1) odd expects R but we have R? Actually odd expects R (since odd=R) and cell is R -> ok. At (3,1) even expects W -> ok. So assignment 2 works. So output grid filled accordingly: For each cell, if parity even -> W, odd -> R. That yields chessboard pattern starting with (0,0) even? (0,0) parity 0 -> W; (0,1) odd -> R; etc. That gives alternating rows? Actually check output given: They have: WRWRWR RWRWRW WRWRWR RWRWRW That's exactly pattern: (0,0) W, (0,1) R, ... So matches.
Second example: 4 4 .R.W .... .... .... We need to check. Grid: row0: . R . W (positions: (0,0) '.', (0,1) 'R', (0,2) '.', (0,3) 'W') Parities: (0,0)=0, (0,1)=1, (0,2)=0, (0,3)=1. We have R at parity 1, W at parity 1? Actually (0,3) parity 1 and is 'W'. So parity 1 has both R and W => conflict because all same parity cells must have same color. So no assignment works. Output NO. Indeed.
Third example: 5 1 vertical: R W R W R Indices: row0 parity0? Actually (0,0) parity 0 -> R, (1,0) parity 1 -> W, (2,0) parity 0 -> R, (3,0) parity1 -> W, (4,0) parity0 -> R. So parity0 always R, parity1 always W. This matches both assignments? Check assignment1: even=R odd=W -> matches all. So valid. Output YES and same grid. That's fine.
Thus solution is straightforward.
However, must ensure to output grid only if YES. Also, the problem says "YES" and "NO" are case-insensitive in output; but better to output uppercase for clarity.
Implementation details: Read t. For each test case, read n,m. Then read n lines. Store as list of strings. We'll perhaps convert to list of list for mutability.
Algorithm: for each test case: n,m = map(int,input().split()) grid = [list(input().strip()) for _ in range(n)] # two options valid = False for (even_color, odd_color) in [('R','W'), ('W','R')]: ok = True for i in range(n): for j in range(m): if grid[i][j] != '.': parity = (i+j)%2 expected = even_color if parity==0 else odd_color if grid[i][j] != expected: ok = False break if not ok: break if ok: # assign result = [row[:] for row in grid] # copy for i in range(n): for j in range(m): if result[i][j] == '.': parity = (i+j)%2 result[i][j] = even_color if parity==0 else odd_color # output YES and grid print("YES") for row in result: print(''.join(row)) valid = True break if not valid: print("NO")
Potential pitfalls: There might be cases where there is a pre-colored cell but the parity mapping could be ambiguous? But we check both.
Time complexity: O(t * n * m) which is fine.
Edge case: n,m = 1? Then grid has one cell, and condition "neighbors" are none, so any color works? Actually if it's pre-colored, it's okay. If it's '.', we can assign either? But the parity mapping would force one color depending on assignment? Actually if there is no pre-colored cell, both assignments are valid, and we can choose either. But the rule is that every red cell only has white neighbors and every white cell only has red neighbors. For a single cell with no neighbors, that condition is vacuously true regardless of its color. However, if we assign according to a fixed assignment, we get a specific color. That's fine. The problem says "print any". So either assignment works. So our algorithm will pick the first assignment (even=R odd=W) and fill accordingly. That yields a valid grid because there are no constraints from neighbors. So okay.
But wait: Could there be a scenario where the grid is not necessarily bipartite? The grid graph is always bipartite because it's a planar grid. So yes.
Thus answer is simple.
Now, some might think about checking adjacency of pre-colored cells directly, but parity check is enough.
Thus solution ready.
However, before finalizing, I'll double-check problem statement: "Your job is to colour the blank cells red or white so that every red cell only has white neighbours (and no red ones) and every white cell only has red neighbours (and no white ones)." This implies that a red cell must have all its neighbors white; but also it says "only has white neighbours". That suggests that if a cell has at least one neighbor, they must all be white. That is equivalent to no adjacent red-red. But is it equivalent to no adjacent same color? Actually if a red cell has all white neighbors, then no neighbor is red. That means no adjacent red-red. Similarly, white cell must have all red neighbors, so no adjacent white-white. So indeed the condition is exactly that adjacent cells must be different colors. So it's proper 2-coloring.
Thus the parity approach is correct.
Now, I'll consider potential trap: The grid might have pre-colored cells that create conflict not just based on parity but also due to something else? For example, consider a cycle of odd length? But grid graph bipartite, no odd cycles. So parity sufficient.
Another nuance: Could a cell have no neighbors (isolated)? That's only if n=m=1. In that case, any color works, but parity mapping gives either R or W, but it's fine.
Thus we can implement.
But is there any case where the grid might have '.' but the parity mapping forced by pre-colored cells conflicts with adjacency? That's covered.
Thus solution is as above.
Now, I recall known Codeforces problem: "1195B? Actually it's "1391A Suborrays"? Not that. There's a problem "1365A" etc. But this specific problem: I think it's from Codeforces Round #1515 Div. 2? Actually it's "1537C? Not sure. It might be "1472C"? Wait, there is a problem called "Red-Blue Grid" or "R and W". It's similar to CF problem "1395A" or "1538A"? Actually I recall CF 1371B? I'd better not get distracted.
But let me double-check that the parity approach is indeed correct for all cases. I'll consider a more complex scenario: Suppose we have a pre-colored red cell at (0,0) and another pre-colored red cell at (1,1). Are they adjacent? (0,0) and (1,1) share a corner, not an edge, so not neighbors. So they can be same color. Parity: (0,0) parity 0, (1,1) parity (1+1)=2 mod2=0, both parity 0. According to parity mapping, all cells with parity 0 must be same color. So if both are red, that's consistent (they both require parity0=red). So good. So parity mapping holds.
Now consider red at (0,0) and white at (1,0). They are adjacent (vertical). (0,0) parity 0, (1,0) parity 1. So they have opposite parity, and they have opposite colors, so consistent with assignment. So parity mapping holds.
Thus indeed constraints from adjacency and parity are equivalent.
Thus solution stands.
Now, implement.
But wait: The input format: The example shows a blank line before the test cases? Actually Input shows:
3 4 6 .R.... ...... ...... .W.... 4 4 .R.W .... .... .... 5 1 R W R W R
No blank line, it's fine.
Now, about output: For each test case, output YES/NO and optionally the grid. I'll print in uppercase YES/NO.
Now, test with given examples. Let's simulate quickly.
Now, think about memory: not an issue.
Now, final answer.
But as the problem is so trivial, I'd like to consider if there is any hidden requirement: For example, "every red cell only has white neighbours" means that if a red cell has a neighbor, that neighbor must be white. But also, if a red cell has no neighbors, it's fine. So still.
Thus answer.
However, maybe there is a nuance: The condition is "only has white neighbours", meaning that all its neighbours are white; but does it also require that it has at least one neighbor? No, only if neighbors exist. So it's just "no red neighbor".
Thus fine.
Now, I will produce the solution.
But before finalizing, let me think if there's any scenario where the pre-colored cells do not conflict with parity but still cause impossibility because of constraints on multiple neighbors? Since parity forces a unique color for each cell, if all pre-colored cells satisfy the parity mapping, then we can assign accordingly and it will be consistent: For any edge between two cells, their parities differ, so they get opposite colors by construction. So all adjacency constraints satisfied. So it's sufficient.
Thus solution is correct.
I'll code accordingly.
But also note: There is a known trick: if there are no pre-colored cells, we can always output a pattern. But our code handles that.
Potential issues: Input reading: there may be spaces? But each line is a string without spaces. So fine.
Now, I'll produce the final answer.
But the problem statement mentions "Today we will be playing a red and white colouring game (no, this is not the Russian Civil War; these are just the colours of the Canadian flag)." So it's just a fun statement.
Alright.
Now, final answer: I will output code in python.
Implementation:
def solve(): import sys data = sys.stdin.read().splitlines() it = iter(data) t = int(next(it)) out_lines = [] for _ in range(t): while True: line = next(it).strip() if line != '': break n, m = map(int, line.split()) grid = [] for i in range(n): grid.append(list(next(it).rstrip('\n'))) # Try two assignments found = False for (even, odd) in [('R','W'), ('W','R')]: ok = True for i in range(n): for j in range(m): ch = grid[i][j] if ch != '.': parity = (i+j) & 1 expected = even if parity == 0 else odd if ch != expected: ok = False break if not ok: break if ok: # build result result = [list(row) for row in grid] # copy for i in range(n): for j in range(m): if result[i][j] == '.': parity = (i+j) & 1 result[i][j] = even if parity == 0 else odd out_lines.append("YES") for i in range(n): out_lines.append(''.join(result[i])) found = True break if not found: out_lines.append("NO") sys.stdout.write("\n".join(out_lines))
But careful: There might be empty lines between test cases? The input probably doesn't have empty lines. However, sometimes there are blank lines after reading n,m? Actually reading line by line: The line after n,m contains the first row. So no blank lines. So the while loop for skipping empty lines is unnecessary and could cause skipping lines incorrectly. I'll remove that.
Simplify: For each test case, read n,m from next line (strip). Then read n lines.
But careful: When reading using sys.stdin.read().splitlines(), blank lines are included as empty strings. However, the input may not contain blank lines. But sometimes there might be trailing newline. But safe to handle: we can just iterate lines and skip empty lines? But better to use a more robust approach: Use sys.stdin.readline() inside loop.
Given that t <= 100, we can just use sys.stdin.readline.
I'll implement with sys.stdin.readline for simplicity.
Here's code:
import sys
def solve(): input = sys.stdin.readline t = int(input().strip()) for _ in range(t): # read n,m: sometimes there might be empty lines? Use while loop to skip empty line = input() while line.strip() == '': line = input() n, m = map(int, line.split()) grid = [] for i in range(n): row = input().rstrip('\n') # Possibly row might be empty? Shouldn't. grid.append(list(row)) # Try assignments found = False for (even, odd) in [('R','W'), ('W','R')]: ok = True for i in range(n): for j in range(m): ch = grid[i][j] if ch != '.': if ((i+j) & 1) == 0: if ch != even: ok = False break else: if ch != odd: ok = False break if not ok: break if ok: # build output out_grid = [list(row) for row in grid] for i in range(n): for j in range(m): if out_grid[i][j] == '.': out_grid[i][j] = even if ((i+j) & 1) == 0 else odd print("YES") for row in out_grid: print(''.join(row)) found = True break if not found: print("NO")
if name == "main": solve()
That should work.
But we must ensure to convert row strings to list for mutability; for printing we can join.
Now, check for large input: fine.
Thus final answer.
But let's double-check with second example: pre-colored .R.W etc. Our code will find both assignments fail, print NO. Good.
Edge case: Suppose n=2,m=2 grid: R . . . We have R at (0,0) parity 0. Both assignments: For even=R, odd=W, (0,0) expects R -> ok. So valid. Fill: (0,0) R, (0,1) odd -> W, (1,0) odd -> W, (1,1) even -> R. Check adjacency: (0,0) adjacent to (0,1) W ok, (1,0) W ok; (0,1) adjacent to (0,0) R, (1,1) R? Actually (0,1) adjacent to (0,0) R and (1,1) R? Wait (0,1) neighbors: up none, down (1,1) parity? (1,1) even=R, so (0,1) W neighbor R? That's fine, but also neighbor left (0,0) R. So both neighbors are R, which are opposite to W. Good. But note (0,1) also has right neighbor? no. So proper.
But there is a potential issue: In this assignment, (1,0) is W and (1,1) is R, adjacent: (1,0) neighbor (1,1) R opposite. So fine.
Thus ok.
Now, what about grid with pre-colored at both parities but same color? That would be invalid because if even=R and odd=W, but we have a cell at odd parity that is R? Actually if same color appears on both parities, then for any assignment, one parity would have that color and the other opposite, but both parities have that same color, impossible. So check: Example: pre-colored R at (0,0) parity0 and R at (0,1) parity1. Then for assignment even=R odd=W, (0,1) odd expects W but is R -> conflict. For even=W odd=R, (0,0) even expects W but is R -> conflict. So NO. Good.
Thus solution correct.
I'll produce final answer.
But there is another nuance: The problem statement says: "Your job is to colour the blank cells red or white so that every red cell only has white neighbours (and no red ones) and every white cell only has red neighbours (and no white ones)." This is a bit stronger: it says "only has white neighbours" meaning that all neighbors are white. But if a cell has neighbors, they must all be white. That is exactly the condition of proper 2-coloring. However, consider a cell with multiple neighbors: it requires that all are opposite color. That's consistent.
One might misinterpret: It might also require that a red cell must have at least one neighbor? No.
Thus all good.
Now, final answer.
But wait: The problem may be trick: What about cells that are '.' but their neighbors are pre-colored and force a particular color? That's handled by parity anyway.
Alright.
Now, I'll produce final answer.
But before final, let's think if there is any case where the parity approach could produce a conflict with the "only has white neighbours" condition due to the fact that a red cell might have a neighbor that is white, but also that neighbor might have a neighbor that is white? No, that's not relevant.
Thus solution is done.
Now, I will output the final code.
But the user asked to respond with a solution. Possibly they want a reasoning and code. Since it's a chat, I'll provide explanation and code.
Let me prepare a comprehensive answer.
First, describe the observation: The condition is equivalent to a proper 2-coloring of the grid graph. Since the grid graph is bipartite, we can assign colors based on parity (i+j) mod 2. The pre-colored cells restrict which color each parity class can take. So we just need to check two possible assignments: all even cells R / odd W, or even W / odd R. If one of them matches all pre-colored cells, we can fill '.' accordingly and output; otherwise impossible.
Then provide code.
I'll ensure code uses fast I/O and handles possibly blank lines (though not needed, but safe).
Ok, final. ```python
import sys
def solve() -> None: input = sys.stdin.readline t = int(input()) for _ in range(t): # read n and m, skip possible empty lines line = input() while line.strip() == '': line = input() n, m = map(int, line.split())
grid = [list(input().rstrip()) for _ in range(n)] found = False # two possible assignments: (even parity, odd parity) for even, odd in [('R', 'W'), ('W', 'R')]: ok = True for i in range(n): for j in range(m): ch = grid[i][j] if ch != '.': parity = (i + j) & 1 expected = even if parity == 0 else odd if ch != expected: ok = False break if not ok: break if ok: # build the answer grid ans = [row[:] for row in grid] # shallow copy of lists for i in range(n): for j in range(m): if ans[i][j] == '.': parity = (i + j) & 1 ans[i][j] = even if parity == 0 else odd print("YES") for row in ans: print(''.join(row)) found = True break if not found: print("NO")if name == "main": solve()