记忆化搜索的解法
#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N=55,MOD=1e9+7;
int w[N][N];
int f[N][N][13][14];//做记忆化存储
int n,m,k;
int dx[2]={1,0},dy[2]={0,1};
int dfs(int x,int y,int cnt,int mx)
{
if(x==n&&y==m) return k==cnt;//结束条件,如果dfs的数量正好等于k,那么就算作一种方案
if(f[x][y][cnt][mx]!=-1) return f[x][y][cnt][mx];//如果之前保存过类似的值,那么就不用再搜了
int res=0;
for(int i=0;i<2;i++)
{
int a=dx[i]+x,b=dy[i]+y;
if(a<1||a>n||b<1||b>m) continue;
//如果满足条件,就拿这个物品
if(w[a][b]>mx&&cnt<k) res=(res+dfs(a,b,cnt+1,w[a][b]))%MOD;
//不拿这个物品
res=(res+dfs(a,b,cnt,mx))%MOD;
}
//更新记忆化搜索的值
f[x][y][cnt][mx]=res;
return res;
}
signed main()
{
cin>>n>>m>>k;
//将f设置为-1,不设置为0的原因是价值可能为0
memset(f,-1,sizeof f);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>w[i][j];
w[i][j]++;
}
cout<<(dfs(1,1,0,0)+dfs(1,1,1,w[1][1]))%MOD<<endl;
return 0;
}