问题描述
#include<iostream> #include<string.h> using namespace std; long long dp[60][60][15][15]; int map[60][60]; int k,N,M; void dfs(int n,int m,int k1,int c){ if(dp[n][m][k1][c]!=-1) return; dp[n][m][k1][c]=0; if(k1==k&&n==N&&m==M) dp[n][m][k1][c]=1; if(map[n][m]>c&&k1<k){ dfs(n,m,k1+1,map[n][m]);dp[n][m][k1][c]+=dp[n][m][k1+1][map[n][m]]; dp[n][m][k1][c]%=1000000007; } if(n<N) { dfs(n+1,m,k1,c);dp[n][m][k1][c]+=dp[n+1][m][k1][c]; dp[n][m][k1][c]%=1000000007; } if(m<M){ dfs(n,m+1,k1,c);dp[n][m][k1][c]+=dp[n][m+1][k1][c]; dp[n][m][k1][c]%=1000000007; } } int main(){ cin>>N>>M>>k; for(int i=1;i<=N;i++){ for(int j=1;j<=M;j++){ cin>>map[i][j];map[i][j]++; } } memset(dp,-1,sizeof(dp)); dfs(1,1,0,0); cout<<dp[1][1][0][0]<<endl; return 0; }
提交结果:
原文:http://www.cnblogs.com/yifan2016/p/5254956.html