I'm preparing for the ACM competition in my country and i'm pretty stuck with this problem, I don't know what algorithm to use either... Given a puzzle pattern you need to tell if it can be constructed only by using pieces with the pieces that have L-shape (as shown on the right image below).
So in this example answer is YES because pattern in the left can be constructed by this piece. Pieces are always the same, pattern is given in the input.
Input
The first line of input contains one positive integer T (1 <= T <= 100), the number of test cases.
Each test case starts with a line that contains two integers H and W (1 <= H, W <= 500), which represent the height and width of the grid containing the pattern. The following H lines, each containing W characters, denote the grid. Each character is either 'R' (red), 'W' (white) or '.' (empty space). Each grid contains at least one 'R' or 'W' character.
Output
For each test case, on a separate line, output either 'YES' if it is possible to construct the pattern with the puzzle pieces, or 'NO' otherwise.
Constraints
Time limit: 15 seconds
Memory limit: 64 megabytes
Examples
input output
2 YES
3 3 NO
W..
RW.
WRW
3 4
RWW.
WWRW
..WR
It's pretty simple — you're given a bipartite graph (the red cells are vertices in one part, the white ones in the other) and are asked if we can match each vertex in the red part to exactly 2 vertices in the white part, something like 2-1 matching. The classical 1-1 matching can be solved easily using flows, and for 2-1, you just don't take capacities source — red vertices to be 1, but 2.
The constraints are crazy, but that's probably why the TL is 15s...