题目描述

就像人类喜欢跳格子游戏一样,FJ的奶牛们发明了一种新的跳格子游戏。虽然这种接近一吨的笨拙的动物玩跳格子游戏几乎总是不愉快地结束,但是这并没有阻止奶牛们在每天下午参加跳格子游戏

游戏在一个R*C的网格上进行,每个格子有一个取值在1-k之间的整数标号,奶牛开始在左上角的格子,目的是通过若干次跳跃后到达右下角的格子,当且仅当格子A和格子B满足如下条件时能从格子A跳到格子B:

1.B格子在A格子的严格右方(B的列号严格大于A的列号)

2.B格子在A格子的严格下方(B的行号严格大于A的行号)

3.B格子的标号和A格子的标号不同

请你帮助奶牛计算出从左上角的格子到右下角的格子一共有多少种不同的方案

输入输出格式

输入格式:

The first line contains the integers R, C, and K.

The next R lines will each contain C integers, each in the range 1..K.

输出格式:

Output the number of different ways one can jump from the top-left square to the bottom-right square, mod 1000000007.

输入输出样例

输入样例#1:

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

输出样例#1:

5


这题很多人用递归,其实递推也是可以的。

反正就是4重循环大暴力。

解题思路见代码

#include<bits/stdc++.h>
using namespace std;
int r,c,k;//行,列,数值限定
int a[751][751];
long long f[751][751]={0};//f[i][j]:左上f[i][j]严格左上方所有点的路径总数之和
int main()
{
scanf("%d%d%d",&r,&c,&k);
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
scanf("%d",&a[i][j]);
f[0][0]=1;
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)//要计算的点
for(int p=0;p<i;p++)
for(int q=0;q<j;q++)//左上方的点
if(a[i][j]!=a[p][q])//审题:要求数值不同
f[i][j]=(f[i][j]+f[p][q])%1000000007;//勿忘mod 1000000007
cout<<f[r-1][c-1]<<endl;
return 0;
}