Two-Colored Dominoes (Codeforces 1863D)
Tags: Greedy, constructive algorithms

There is an $$$n\times m$$$ board divided into cells. There are also some dominoes on this board. Each domino covers two adjacent cells (that is, two cells that share a side), and no two dominoes overlap.Piet thinks that this board is too boring and it needs to be painted. He will paint the cells of the dominoes black and white. He calls the painting beautiful if all of the following conditions hold:  for each domino, one of its cells is painted white and the other is painted black;  for each row, the number of black cells in this row equals the number of white cells in this row;  for each column, the number of black cells in this column equals the number of white cells in this column. Note that the cells that are not covered by dominoes are not painted at all, they are counted as neither black nor white.Help Piet produce a beautiful painting or tell that it is impossible.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10\,000$$$). The description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2\le n, m\le 500$$$).The next $$$n$$$ lines describe the tiling of the board, row by row from top to bottom. Each of these lines contains $$$m$$$ characters, describing the cells in the corresponding row from left to right. Each character is one of U, D, L, R, or ., meaning that the cell is covered with a top, bottom, left, right half of a domino or nothing, respectively. The tiling is guaranteed to be valid.It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$250\,000$$$.

Output: For each test case, output a single integer $$$-1$$$ if a beautiful painting does not exist. Otherwise, print $$$n$$$ lines, each containing $$$m$$$ characters, describing the colors in the corresponding row of a beautiful painting. Every character corresponding to a cell not covered by a domino must be . (a dot), and all other characters must be B if the corresponding cell is black or W if it is white.If there are multiple solutions, print any of them.

Note: In the first test case, the answer is illustrated below:   In the second test case, it is impossible to paint all cells the right way.

Sample Inputs:
3
4 6
..LR..
ULRU..
DLRDUU
..LRDD
5 4
.LR.
.UU.
UDDU
D..D
LR..
2 2
..
..

Sample Outputs:
..WB..
WWBB..
BBWWWB
..BWBW
-1
..
..

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, m) = readInts()
    arr = [readStr() for _ in range(n)]
    ans = [['.'] * m for _ in range(n)]
    for i in range(n):
        curr = 0
        for j in range(m):
            if arr[i][j] == 'U':
                ans[i][j] = 'W' if not curr else 'B'
                ans[i + 1][j] = 'W' if curr else 'B'
                curr ^= 1
        if curr:
            return -1
    for j in range(m):
        curr = 0
        for i in range(n):
            if arr[i][j] == 'L':
                ans[i][j] = 'W' if not curr else 'B'
                ans[i][j + 1] = 'W' if curr else 'B'
                curr ^= 1
        if curr:
            return -1
    return '\n'.join([''.join(each) for each in ans])
for _ in range(int(input())):
    print(solve())

Solution (Python):
from sys import stdin
''

def my_func():
    """"""
    (num_rows, num_columns) = map(int, stdin.readline().split())
    game_board = []
    for _ in range(num_rows):
        game_board.append(list(stdin.readline().strip()))
    left_columns = [[] for _ in range(num_columns)]
    upper_rows = [[] for _ in range(num_rows)]
    for (row_index, row) in enumerate(game_board):
        for (column_index, cell) in enumerate(row):
            if cell == 'L':
                ''
                left_columns[column_index].append(row_index)
            elif cell == 'U':
                upper_rows[row_index].append(column_index)
    is_valid = True
    for left_column in left_columns:
        if len(left_column) % 2 == 1:
            is_valid = False
            break
        ''
    for upper_row in upper_rows:
        if len(upper_row) % 2 == 1:
            is_valid = False
            break
    if not is_valid:
        print(-1)
        return
    for (column_index, left_cell_indices) in enumerate(left_columns):
        for index in range(0, len(left_cell_indices), 2):
            row_index1 = left_cell_indices[index]
            row_index2 = left_cell_indices[index + 1]
            game_board[row_index1][column_index] = 'W'
            game_board[row_index2][column_index] = 'B'
            game_board[row_index1][column_index + 1] = 'B'
            game_board[row_index2][column_index + 1] = 'W'
            ''
    for (row_index, upper_cell_indices) in enumerate(upper_rows):
        for index in range(0, len(upper_cell_indices), 2):
            column_index1 = upper_cell_indices[index]
            column_index2 = upper_cell_indices[index + 1]
            game_board[row_index][column_index1] = 'W'
            game_board[row_index][column_index2] = 'B'
            game_board[row_index + 1][column_index1] = 'B'
            game_board[row_index + 1][column_index2] = 'W'
            ''
    for row in game_board:
        print(''.join(row))
num_tests = int(stdin.readline())
for _ in range(num_tests):
    ''
    my_func()

Solution (Python):
import sys
input = sys.stdin.readline
o = lambda : map(int, input().split())
for _ in range(int(input())):
    (h, c) = o()
    grid = []
    for _ in range(h):
        grid.append(list(input().strip()))
    ans = []
    e = {0: 'W', 1: 'B'}
    flag = True
    t = 0
    for i in range(h):
        for j in range(c):
            if grid[i][j] == 'U':
                grid[i][j] = e[t]
                grid[i + 1][j] = e[(t + 1) % 2]
                t = (t + 1) % 2
        if t:
            flag = False
            break
    if flag:
        for j in range(c):
            for i in range(h):
                if grid[i][j] == 'L':
                    grid[i][j] = e[t]
                    grid[i][j + 1] = e[(t + 1) % 2]
                    t = (t + 1) % 2
            if t:
                flag = False
                break
        if flag:
            for row in grid:
                print(''.join(row))
        else:
            print(-1)
    else:
        print(-1)