Treasure taking from underground palace (memory based deep search)

Portal
Title Description
X The king has a treasure house . yes n x m Matrix of lattice . One treasure per cell . Every baby has a value tag .
The entrance to the underground palace is in the upper left corner , The exit is in the lower right corner .
Xiaoming is taken to the entrance of the underground palace , The king asked him to walk only to the right or down .
When walking through a grid , If the treasure in that lattice is worth more than any treasure in Xiaoming's hand , Xiaoming can pick it up （ Of course , Or not ）.
When Xiaoming comes to the exit , If the baby in his hand happens to be k Pieces of , Then these babies can be given to Xiao Ming .
Input format
The input line 3 It's an integer , Separate with spaces ：n m k (1<=n,m<=50, 1<=k<=12)
Next there is n Row data , Each row has m It's an integer Ci (0<=Ci<=12) Represents the value of the treasure on this grid

Output format
An integer is required , It means just take k Number of action plans for each baby . The number could be large , Export it to 1000000007 Results of die taking .
sample input
2 2 2
1 2
2 1
sample output
2

analysis ： Yes 1000000007 Taking a mold indicates that there is a large amount of data , Use long long Type and memory deep search ;
1、 All baby value plus 1： Because the initial value may be 0,maxn Cannot also be 0 The comparison in the function is changed to >= That's not right. （ It is required that the baby you find is more expensive than the previous one ）maxn by -1 Not good either. Array cannot be negative , So we need to add 1 So the minimum initial value is 1 They don't influence each other
2、 Every time ans Initialize to 0, We have reached a certain point , Each subsequent step corresponds to several situations , therefore dp Represents this step , How many situations can it correspond to , This gradually accumulates , all return The starting point of the last step ans Is the general situation

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1000000007;
ll a[55][55];
ll dp[55][55][15][15];
ll n,m,k;
ll dfs( ll x,ll y,ll maxn,ll t)
{
    
	ll ans=0;
	if(t>k||x>n||y>m) return 0;
	if(dp[x][y][maxn][t]!=-1)
	return dp[x][y][maxn][t];
	if(x==n&&y==m)
	{
    
		if( t==k || (t==k-1&&a[x][y]>maxn) )
		return 1;
		return 0;
	}
	if(a[x][y]>maxn)// Pick up the baby  
	{
    
		ans+=dfs(x+1,y,a[x][y],t+1);
		ans+=dfs(x,y+1,a[x][y],t+1);
	}
	ans+=dfs(x+1,y,maxn,t);
	ans+=dfs(x,y+1,maxn,t);
// When you meet the right baby, you can pick it up , There are also cases where it is not necessary to pick up , So we have to go through the situation of not picking up  
	ans%=mod;
	dp[x][y][maxn][t]=ans;
	return ans;
}
int main()
{
    
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
    
		scanf("%lld",&a[i][j]);
		a[i][j]+=1; 
	}
	memset(dp,-1,sizeof(dp));
	printf("%lld\n",dfs(1,1,0,0)%mod);
}