题目描述

牛跳房子游戏在一个 $R \times C$ 的网格中进行，每个格子上有一个 $1 \cdots K$ 的数字$( 1 \leq K \leq R \times C )$。

牛从网格的左上角出发，跳到右下角。一次跳跃是合法的，当且仅当满足以下的所有条件：

1. 目标格子与当前所在格子的数字不同；
2. 目标格子至少应在当前格子下一行；
3. 目标格子至少应在当前格子右一列。

现在请你求出：从左上角跳到右下角的合法跳跃的方案数量。

输入格式：第一行输入三个数字，$R , C , K$ .接下来$R$行每行输入$C$ 个数字来描述游戏地图。保证每个数字都在$1 \leq K$的范围内。

输出格式：输出总方案数 $ \mod 10^9+7$ 的结果。

输入格式

第一行输入三个数字， $R , C , K$.接下来 $R$ 行每行输入 $C$ 个数字来描述游戏地图。保证每个数字都在 $1 \leq K$ 的范围内。

输出格式

输出总方案数 $\mod 10^9+7$ 的结果。

输入输出样例

输入 #1

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

输出 #1

5

分析

如图，当计算到点 $(3,3)$ 即红色点时，这个点的方案数是所有可以跳到这个点的点的方案数之和，也就是点 $(1,1),(1,2),(2,1),(2,2)$ 即黄色点的方案数，于是我们很容易就可以得到状态转移方程，注意边界为点 $(1,1)$ 的方案数，因为显然我们会从这个点开始计算且只有开始计算这一种方式来到达点 $(1,1)$， 因此它的方案数为 $1$。

代码

#include<bits/stdc++.h>
#define int long long
const int MOD = 1000000007;
using namespace std;
int r,c,k;
int f[1001][1001],a[1001][1001];
signed main(){
//    freopen("hopscotch.in","r",stdin);
//    freopen("hopscotch.out","w",stdout);
    scanf("%lld%lld%lld",&r,&c,&k);
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            scanf("%lld",&a[i][j]);
        }
    }
    f[1][1]=1;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            for(int m=1;m<i;m++){
                for(int n=1;n<j;n++){
                    if(a[i][j]!=a[m][n]){
                        f[i][j]+=f[m][n];
                        f[i][j]%=MOD; 
                    }
                }
            }
        }
    }
    printf("%lld",f[r][c]);
    return 0;
}