地宫取宝DP解法

解题思路:

注意事项:

参考代码:

#include<iostream>
using namespace std;
const int N=60,mod=1e9+7;
int f[N][N][13][14];
int a[N][N];
int n,m,k;
int main()
{
   cin>>n>>m>>k;
   for(int i=1;i<=n;i++){
       for(int j=1;j<=m;j++){
           cin>>a[i][j];
           a[i][j]++;
       }
   }
   f[1][1][1][a[1][1]]=1;
   f[1][1][0][0]=1;
   for(int i=1;i<=n;i++){
       for(int j=1;j<=m;j++){
           for(int u=0;u<=k;u++){
               for(int v=0;v<=13;v++){
                   f[i][j][u][v]=(f[i][j][u][v]+f[i-1][j][u][v])%mod;
                   f[i][j][u][v]=(f[i][j][u][v]+f[i][j-1][u][v])%mod;
                   if(u>0&&v==a[i][j]){
                       for(int c=0;c<v;c++){
                           f[i][j][u][v]=(f[i][j][u][v]+f[i-1][j][u-1][c])%mod;
                           f[i][j][u][v]=(f[i][j][u][v]+f[i][j-1][u-1][c])%mod;
                       }
                   }
               }
           }
       }
   }
   int res=0;
   for(int i=1;i<=13;i++) res=(res+f[n][m][k][i])%mod;
   cout<<res;
   return 0;
}