本文主要是介绍地宫取宝dfs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
分析：
矩阵里的每一个位置都有标记，要求的问题是：有几种方法能完成这个规定。
那么，我们只需要计算从开始(1,1)到最后(n,m)的深度优先搜索中，有几个是满足要求的即为正确答案。
有个要求是，如果一个格子中的价值比已经拿的都大，那么可以选择拿或者不拿，这里就有两种情况，一个是以手中的最大值mx做标准，另一种是以c[i][j]做标准，两种情况。
代码示例：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 55,p=1e9+7;
int n,m,k,c[N][N];
int dx[]={0,1};
int dy[]={1,0};
int dp[N][N][15][15];
bool inmp(int x,int y){return (x>=1&&x<=n&&y>=1&&y<=m);
}
ll dfs(int x,int y,int mx,int cnt){if(x==n&&y==m)return cnt==k;if(dp[x][y][mx][cnt]!=-1)return dp[x][y][mx][cnt];ll res=0;for(int i=0;i<2;i++){int nx=x+dx[i];int ny=y+dy[i];if(!inmp(nx,ny))continue;// 拿这个 if(c[nx][ny]>mx&&cnt<k)res=(res+dfs(nx,ny,c[nx][ny],cnt+1))%p;// 不拿这个res=(res+dfs(nx,ny,mx,cnt))%p;}return dp[x][y][mx][cnt]=res;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);memset(dp,-1,sizeof(dp));cin>>n>>m>>k;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>c[i][j];c[i][j]++;}cout<<(dfs(1,1,0,0)+dfs(1,1,c[1][1],1))%p;return 0;
}
/*可以设置状态dp[x][y][mx][cnt]表示走到(x,y),手中有cnt个宝贝且最大值为mx的方案数 */
这篇关于地宫取宝dfs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
