Cow Hopscotch (Silver)

题目描述

就像人类喜欢玩跳房子一样，农夫约翰的奶牛们也为自己发明了一种变体来玩。由于参与者是笨拙且体重接近一吨的动物，奶牛跳房子几乎总是以灾难告终，但这却出乎意料地没有阻止她们几乎每个下午都尝试玩。\n游戏在一个 $R$ 行 $C$ 列的网格上进行（$2 <= R <= 100$, $2 <= C <= 100$），其中每个格子都标有一个 $1..K$ 范围内的整数（$1 <= K <= R*C$）。奶牛从左上角格子出发，通过一系列跳跃移动到右下角格子。一次跳跃当且仅当满足以下条件时才是合法的：\n1) 你要跳到的格子上的整数与当前格子上的整数不同；\n2) 你要跳到的格子至少在当前格子的下一行（行号更大至少 1）；\n3) 你要跳到的格子至少在当前格子的下一列（列号更大至少 1）。\n请帮助奶牛计算：从左上角格子跳到右下角格子，满足上述条件的不同合法跳跃序列有多少种。

输入格式

第一行包含整数 $R$, $C$, $K$。\n接下来的 $R$ 行每行包含 $C$ 个整数，每个都在 $1..K$ 范围内。

输出格式

输出从左上角格子跳到右下角格子的不同方式数，对 $1000000007$ 取模。

4 4 4\n1 1 1 1\n1 3 2 1\n1 2 4 1\n1 1 1 1

5

提示

[题目致谢：Nick Wu, 2015]

标签: USACO|2015|Silver

来源

USACO|2015|Silver