Cow Hopscotch (Bronze)

题目描述

就像人类喜欢玩跳房子一样，农夫约翰的奶牛们也发明了一种自己的变体游戏。由于参与者是体重接近一吨、动作笨拙的动物，“奶牛跳房子”几乎总会以灾难告终，但这出乎意料地并没有阻止奶牛们几乎每天下午都尝试去玩。\n\n游戏在一个 $R$ 行 $C$ 列的网格上进行（2 <= R <= 15, 2 <= C <= 15），每个格子被涂成红色或蓝色。奶牛从左上角的格子出发，通过一系列跳跃移动到右下角的格子。一次跳跃当且仅当满足以下条件时才是合法的：\n1) 你跳到的格子颜色与当前所在格子不同，\n2) 你跳到的格子所在行至少比当前格子低一行，\n3) 你跳到的格子所在列至少比当前格子右一列。\n\n请帮助奶牛计算：从左上角跳到右下角，一共有多少种不同的合法跳跃序列。

输入格式

第一行包含两个整数 $R$ 和 $C$。接下来的 $R$ 行每行包含 $C$ 个字符。每个字符为 'R' 或 'B'，分别表示红色格子或蓝色格子。

输出格式

输出从左上角跳到右下角的不同跳跃方式数量。

4 4\nRRRR\nRRBR\nRBBR\nRRRR

3

提示

[题目贡献：Nick Wu, 2015]

标签: USACO|2015|Bronze

来源

USACO|2015|Bronze