【蓝桥杯真题】地宫取宝(搜索->记忆化搜索详解)

时间:2023-12-16 23:36:26

链接

[蓝桥杯][2014年第五届真题]地宫取宝

题目描述

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 3 2

1 2 3

2 1 5

样例输出

14

思路

这个题目分析题意可以得到是一个dfs递归的题目,因为要搜索出每一种可能的情况。并且这个问题不需要回溯(只是在地图上有两个方向可以选择,并且可以选择是否拾起物体,回溯是不取这个物体,这个物体需要另做他用,这个问题不需要考虑)。

接下来就是如何设计这个dfs。

1.首先考虑递归参数。当前走到的地图的位置(i,j),当前选择出的物品的数目cnt,当前的最大物品的质量max。

2.递归出口是走到了地图的出口,如果当前物品数量等于k,ans++,如果当前的物品数量等于k-1并且最后一个物品的重量大于max,ans++。另外一个递归出口是走出边际和选择的物品数量大于k。

dfs代码如下:

void dfs(int i,int j,int cnt,int max){
if(cnt>k||i>n||j>m)return;
if(i==n&&j==m){
if(cnt==k||(cnt==k-1&&maze[i][j]>max))(++ans)%MOD;
return;
}
dfs(i,j+1,cnt,max);
dfs(i+1,j,cnt,max);
if(maze[i][j]>max){
dfs(i+1,j,cnt+1,maze[i][j]);
dfs(i,j+1,cnt+1,maze[i][j]);
}
}

这样会超时,因为在每一点可以选择的方案是2 or 4,这是一个指数级别搜索量。考虑到到达某一个点会有多种方案并且他们的状态是相同的,所以之前的方案存在重复计算,应该设计记忆型搜索,记忆递归函数应该返回一个值。

代码

//	递归改记忆型递归并不复杂,由于存在重复计算的情况
// 重复计算,就是dfs的参数一样,也就是达到目前的状态可能有许多方式,运用记忆化搜索,对于重复的位置只计算一次。
// 所以用一个标记数组,数组的参数与dfs的参数相同
long long dfs2(int i,int j,int cnt,int max){
//查缓存
if(cache[i][j][cnt][max+1]!=-1)return cache[i][j][cnt][max+1];
long long ans=0;//记得一定是局部变量
if(cnt>k||i>n||j>m)return 0;
if(i==n&&j==m){
if(cnt==k||(cnt==k-1&&maze[i][j]>max))++ans;
return ans;
}
ans+=dfs2(i,j+1,cnt,max);
ans+=dfs2(i+1,j,cnt,max);
if(maze[i][j]>max){
ans+=dfs2(i+1,j,cnt+1,maze[i][j]);
ans+=dfs2(i,j+1,cnt+1,maze[i][j]);
}
// 在return之前一定写缓存
cache[i][j][cnt][max+1]=ans%MOD;
return ans%MOD;
}

完整代码

#include<iostream>
#include<cmath>
#include<sstream>
#include<cstring>
using namespace std;
const int MOD=1000000007;
const int N=55;
int maze[N][N];
int vis[N][N];
int n,m,k;
long long ans=0;
int cache[N][N][13][14];
void dfs(int i,int j,int cnt,int max){
if(cnt>k||i>n||j>m)return;
if(i==n&&j==m){
if(cnt==k||(cnt==k-1&&maze[i][j]>max))(++ans)%MOD;
return;
}
dfs(i,j+1,cnt,max);
dfs(i+1,j,cnt,max);
if(maze[i][j]>max){
dfs(i+1,j,cnt+1,maze[i][j]);
dfs(i,j+1,cnt+1,maze[i][j]);
}
}
// 递归改记忆型递归并不复杂,由于存在重复计算的情况
// 重复计算,就是dfs的参数一样,也就是达到目前的状态可能有许多方式,运用记忆化搜索,对于重复的位置只计算一次。
// 所以用一个标记数组,数组的参数与dfs的参数相同
long long dfs2(int i,int j,int cnt,int max){
//查缓存
if(cache[i][j][cnt][max+1]!=-1)return cache[i][j][cnt][max+1];
long long ans=0;//记得一定是局部变量
if(cnt>k||i>n||j>m)return 0;
if(i==n&&j==m){
if(cnt==k||(cnt==k-1&&maze[i][j]>max))++ans;
return ans;
}
ans+=dfs2(i,j+1,cnt,max);
ans+=dfs2(i+1,j,cnt,max);
if(maze[i][j]>max){
ans+=dfs2(i+1,j,cnt+1,maze[i][j]);
ans+=dfs2(i,j+1,cnt+1,maze[i][j]);
}
// 在return之前一定写缓存
cache[i][j][cnt][max+1]=ans%MOD;
return ans%MOD;
}
int main(){ cin>>n>>m>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>maze[i][j];
}
memset(cache,-1,sizeof(cache));
// dfs(1,1,0,-1);
cout<<dfs2(1,1,0,-1)<<endl;
//由于max最开始的值为-1,由于数组中不能访问-1.,所以做一个技巧,max+1
return 0;
}