15113번 - Grid Coloring 다국어

You have an m-by-n grid of squares that you wish to color. You may color each square either red or blue, subject to the following constraints:

• Every square must be colored.
• Colors of some squares are already decided (red or blue), and cannot be changed.
• For each blue square, all squares in the rectangle from the top left of the grid to that square must also be blue.

Given these constraints, how many distinct colorings of the grid are there? The grid cannot be rotated.

The first line of input consists of two space-separated integers m and n (1 ≤ m, n ≤ 30).

Each of the next m lines contains n characters, representing the grid. Character ‘B’ indicates squares that are already colored blue. Similarly, ‘R’ indicates red squares. Character ‘.’ indicates squares that are not colored yet.

Print, on a single line, the number of distinct colorings possible.

For the first sample, the 6 ways are:

BB   BB   BR   BR   BB   BB
BB   BR   BR   BR   BR   BB
BR   BR   BR   RR   RR   RR