Recueillir des trésors dans le palais souterrain (recherche de mémoire profonde)

Porte de transfert
Description du sujet
X Le Roi a un trésor souterrain.- Oui. n x m Une matrice de treillis.Un bébé par grille.Chaque bébé porte une étiquette de valeur.
L'entrée du palais souterrain est en haut à gauche,La sortie est en bas à droite.
Xiao Ming a été emmené à l'entrée du palais souterrain,Le roi lui demanda de marcher seulement à droite ou en bas.
En traversant une grille,Si la valeur du bébé dans cette grille est plus grande que n'importe quel bébé dans la main de Xiao Ming,Xiao Ming peut le ramasser（Bien sûr.,Ou ne pas prendre）.
Quand Xiao Ming est arrivé à la sortie,Si le bébé entre ses mains se trouve êtrekPièce (s),Alors ces bébés peuvent être donnés à Xiaoming.
Format d'entrée
Entrez une ligne3Nombre entier,Séparer par des espaces：n m k (1<=n,m<=50, 1<=k<=12)
Ensuite, il y a n Données de ligne,Chaque ligne a m Nombre entier Ci (0<=Ci<=12)Représente la valeur des trésors sur cette grille

Format de sortie
Exiger la sortie d'un entier,Ça veut dire juste prendrekNombre de plans d'action par bébé.Le nombre peut être énorme,La sortie correspond à 1000000007 Résultats de l'extraction des moules.
Exemple d'entrée
2 2 2
1 2
2 1
Exemple de sortie
2

Analyse：C'est exact. 1000000007 La quantité de données est très importante,Utiliserlong longType et recherche de mémoire;
1、Tous les bébés valent plus1：Parce que la valeur initiale peut être0,maxnNon, et en même temps.0 Changez la fonction de comparaison en>=Ce n'est pas juste.（ Demander que les bébés soient plus chers qu'avant ）maxnPour-1Pas du tout. Le tableau ne peut pas être négatif , Alors ajoutez 1 Cette valeur initiale minimale est 1 Aucune influence mutuelle
2、Chaque foisansInitialiser comme0, C'est arrivé à un certain point , Plusieurs situations correspondent à chacune des étapes suivantes ,Alors...dp Les délégués sont arrivés à ce stade , Combien de situations peuvent correspondre , Ça s'accumule progressivement ,Tousreturn Au début de la première étape suivante ans C'est la situation générale

#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)// Ramasse le bébé.  
	{
    
		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);
// Quand on rencontre le bon bébé, on le ramasse , Il y a aussi des situations où vous ne pouvez pas ramasser , C'est pour ça qu'il faut traverser la situation de ne pas ramasser  
	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);
}