【跳跃游戏】

题目背景

USACO 2015 FEBRUARY CONTEST,SILVER——PROBLEM 2 COW HOPSCOTCH

题目描述

有一种跳跃游戏是在一个 R 行、C 列(2<=R<=100,2<=C<=100)的网格中进行,其中每一个小方格被标记为一个 1..K(1<=K<=R*C)范围的整数。游戏者从左上角开始,然后通过一个跳跃的序列移动到右下角。我们认为一个跳跃是有效的当且仅当:
(1)必须跳到一个与当前出发方格标有不同整数的方格。
(2)你要跳到的方格必须位于当前出发方格的下方。
(3)你要跳到的方格必须位于当前出发方格的右侧。
请你计算出从左上角到右下角的不同有效跳跃方案的个数。
提醒:可以跳斜线,也可以跳到不相邻的格子。

输入格式

第一行包含 3 个整数 R,C 和 K。
接下来 R 行,每行 C 个整数,每个整数的取值范围是 1..K ,表示整个网格。

输出格式

输出从左上角到右下角的不同有效跳跃方案的个数,最后结果 mod 1000000007。

样例数据 1

输入

4 4 4
1 1 1 1
1 3 2 1
1 2 4 1
1 1 1 1

输出

5

备注

【样例说明】

看到数据范围只有100×100直接裸棋盘DP水过了……dp[i][j]记录从(1,1)跳到(i,j)的方案数,很明显直接从左上角找一遍转移过来就行了。

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*