Mock CCC '18 Contest 2 J5/S3 - A Coloring Problem

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 5.0s
Memory limit: 1G

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

An m-by-n grid G is good if every square is colored either red or blue, and if the square in row i, column j is blue, then every square in row k, column l that satisfies k \le i and l \le j must also be colored blue.

You are given a grid that is partially colored in. Count the number of ways to color the remaining squares of the grid such that the grid is good.

Constraints

1 \le m, n \le 30

At least one square in the grid will be ..

Input Specification

The first line contains two space-separated integers m and n.

Each of the next m lines contains n characters representing the grid. Each character is either R to represent a red square, B to represent a blue square, or . to indicate a square that has not been colored.

Output Specification

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

Sample Input

3 2
..
B.
.R

Sample Output

6

Sample Input

7 6
......
.....B
.B..R.
......
...B..
.R....
...R..

Sample Output

3

Sample Input

2 2
R.
.B

Sample Output

0

Comments

There are no comments at the moment.