历届试题 地宫取宝

问题描述

  X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。

  地宫的入口在左上角,出口在右下角。

  小明被带到地宫的入口,国王要求他只能向右或向下行走。

  走过某个格子时,如果那个格子中的宝贝价值比小明手中任意宝贝价值都大,小明就可以拿起它(当然,也可以不拿)。

  当小明走到出口时,如果他手中的宝贝恰好是k件,则这些宝贝就可以送给小明。

  请你帮小明算一算,在给定的局面下,他有多少种不同的行动方案能获得这k件宝贝。

输入格式

  输入一行3个整数,用空格分开:n m k (1<=n,m<=50, 1<=k<=12)

  接下来有 n 行数据,每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值

输出格式

  要求输出一个整数,表示正好取k个宝贝的行动方案数。该数字可能很大,输出它对 1000000007 取模的结果。

样例输入

2 2 2
1 2
2 1

样例输出

2

样例输入

2 3 2
1 2 3
2 1 5

样例输出

14

记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAX 51
const int eps=1000000007;
using namespace std;
int n,m,k;
int dp[50][50][13][13];
int map[MAX][MAX];
int dfs(int i,int j,int num,int max){
//max -1
if(dp[i][j][num][max+1]!=-1) return dp[i][j][num][max+1];
long long cnt=0;
if(i==n&&j==m){
if(map[i][j]>max&&num==k-1) cnt++;
if(num==k) cnt++;
return dp[i][j][num][max+1]=cnt;
}
if(i+1<=n){
if(map[i][j]>max) {
cnt+=dfs(i+1,j,num+1,map[i][j]);
cnt%=eps;
}
cnt+=dfs(i+1,j,num,max);
//!
cnt%=eps;
}
if(j+1<=m){
if(map[i][j]>max) {
cnt+=dfs(i,j+1,num+1,map[i][j]);
cnt%=eps;
}
cnt+=dfs(i,j+1,num,max);
cnt%=eps;
}
dp[i][j][num][max+1]=cnt;
return cnt;
}
int main(){

cin>>n>>m>>k;
//! i从1开始
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
cin>>map[i][j];
}
//!
memset(dp,-1,sizeof(dp));
dfs(1,1,0,-1);
cout<<dp[1][1][0][0];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//超时代码 
#include<iostream>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
#define MAX 100
int n,m,k;
int num[MAX][MAX];
int ans=0;
void dfs(int x,int y,int sum,int max){
//递归终止条件
if(x==n-1&&y==m-1){
if(sum==k-1&&num[x][y]>max) ans++;
if(sum==k) ans++ ;
return;
}
//搜索
//所在的格子的价值比max大
if(x+1<n){
if(num[x][y]>max) dfs(x+1,y,sum+1,num[x][y]);
dfs(x+1,y,sum,max);

}


if(y+1<m){
if(num[x][y]>max) dfs(x,y+1,sum+1,num[x][y]);
dfs(x,y+1,sum,max);//!!

}
}
int main(){
// freopen("y1.txt","r",stdin);
cin>>n>>m>>k;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>num[i][j];
}
}
dfs(0,0,0,-1);
printf("%d\n",ans%1000000007);
}

参考
http://www.voidcn.com/article/p-nloxrfju-zq.html
https://blog.csdn.net/Enjoying_Science/article/details/44944253