蓝桥杯历届试题-地宫取宝 （C++代码）

解题思路:

记忆化搜索。



注意事项:





参考代码:

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 51
#define MOD 1000000007
int map[N][N],n,m,k;
int dp[N][N][15][15];
int dfs(int x,int y,int sum,int max){
	if(dp[x][y][sum][max+1]!=-1)return dp[x][y][sum][max+1];
	int t=0;
	if(x==n-1&&y==m-1){
		if(map[x][y]>max){
			if(sum==k||sum==k-1)t++;
		}
		else if(sum==k)t++;
		return dp[x][y][sum][max+1]=t;
	}
	if(x+1<n){
		if(map[x][y]>max){
			t+=dfs(x+1,y,sum+1,map[x][y]);
			t%=MOD;
		}
		t+=dfs(x+1,y,sum,max);
		t%=MOD;
	}
	if(y+1<m){
		if(map[x][y]>max){
			t+=dfs(x,y+1,sum+1,map[x][y]);
			t%=MOD;
		}
		t+=dfs(x,y+1,sum,max);
		t%=MOD;
	}
	dp[x][y][sum][max+1]=t;
	return dp[x][y][sum][max+1];
} 
int main()
{	
    cin>>n>>m>>k;
    for(int i=0;i<n;i++){
    	for(int j=0;j<m;j++){
    		cin>>map[i][j];
		}
	}
	memset(dp,-1,sizeof(dp));
	dp[0][0][0][0]=dfs(0,0,0,-1);
	cout<<dp[0][0][0][0];
    return 0;
}