Farmer John's cows have invented a variant of Hopscotch. The game is played on an R by C grid (2 <= R <= 15, 2 <= C <= 15), where each square is colored either red or blue. Cows start in the top-left square and move to the bottom-right square by a sequence of jumps, where a jump is valid if and only if:

1) You are jumping to a square of a different color,
2) The square you are jumping to is at least one row below the current square, and
3) The square you are jumping to is at least one column to the right of the current square.

Please help the cows compute the number of different possible sequences of valid jumps from the top-left square to the bottom-right square.

Line 1: R and C. The next R lines each contain C characters, each 'R' (red) or 'B' (blue).

The number of different ways one can jump from the top-left square to the bottom-right square.

riseoj 작성

출처 올림피아드 > USACO > 2014-2015 > February > Bronze