algorithm - ACM: Create pattern given puzzle shape -

algorithm - ACM: Create pattern given puzzle shape -

i'm preparing acm competition in country , i'm pretty stuck problem, don't know algorithm utilize either...

the problem is: given puzzle pattern need tell if can constructed using pieces pieces have l-shape (as shown on right image below).

so in illustration reply yes because pattern in left can constructed piece. pieces same, pattern given in input.

here constraints

input first line of input contains 1 positive integer t (1 <= t <= 100), number of test cases. each test case starts line contains 2 integers h , w (1 <= h, w <= 500), represent height , width of grid containing pattern. next h lines, each containing w characters, denote grid. each character either 'r' (red), 'w' (white) or '.' (empty space). each grid contains @ to the lowest degree 1 'r' or 'w' character. output each test case, on separate line, output either 'yes' if possible build pattern puzzle pieces, or 'no' otherwise. constraints time limit: 15 seconds memory limit: 64 megabytes

example

input output 2 no 3 3 yes w.. rw. wrw 3 4 rww. wwrw ..wr

you know if there n reddish spots, there must 2n white spots. each reddish spot locates l-shape; have determine orientations some l-shapes have more limited number of choices others (for example, reddish spot in corner can have l 1 orientation). if "place" pieces in order how many possible orientations have (small big), can limit number of possibilities considered. if pattern (or becomes) disjoint, can solve each of disconnected sections independently in sequence (as opposed bouncing between sections). might not worth effort observe such occurrences, although if place pieces cause such divisions, help speed things up.

algorithm