本文主要是介绍蓝桥杯c/c++预选赛 地宫取宝，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述
X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。
地宫的入口在左上角，出口在右下角。
小明被带到地宫的入口，国王要求他只能向右或向下行走。
走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。
当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。
请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。
地宫的入口在左上角，出口在右下角。
小明被带到地宫的入口，国王要求他只能向右或向下行走。
走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。
当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。
请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。
输入格式
输入一行3个整数，用空格分开：n m k (1<=n,m<=50, 1<=k<=12)
接下来有 n 行数据，每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值
接下来有 n 行数据，每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值
输出格式
要求输出一个整数，表示正好取k个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 取模的结果。
样例输入
2 2 2
1 2
2 1
1 2
2 1
样例输出
2
样例输入
2 3 2
1 2 3
2 1 5
1 2 3
2 1 5
样例输出
14
这个我就说一下我的思路，还是用一个四维数组表示状态dp[i][j][k][n]代表到map[i][j]时最大值为k，
当前有n个物品时的走法
#include<stdio.h>
#include<string.h>
#define N 1000000007
int map[55][55];
int dp[55][55][15][15]; //dp[i][j][k][n]代表到map[i][j]时最大值为k，当前有n个物品
int m, n, k;
int dfs(int i, int j, int max, int num){if (dp[i][j][max+1][num] != -1)return dp[i][j][max+1][num];int t = 0;if (map[i][j] > max && num < k){if (i < n - 1 || (j == m - 1 && i == n - 1)) //如果到达出口的位置，再往下走一格t = (t + dfs(i + 1, j, map[i][j], num + 1)) % N;if (j < m - 1)t = (t + dfs(i, j + 1, map[i][j], num + 1)) % N;}if (i < n - 1 || (j == m - 1 && i == n - 1))t = (t + dfs(i + 1, j, max, num)) % N;if (j < m - 1)t = (t + dfs(i, j + 1, max, num)) % N;return dp[i][j][max+1][num] = t;
}
int main(){scanf("%d%d%d", &n, &m, &k);int i, j;for (i = 0; i < n; i++)for (j = 0; j < m; j++){scanf("%d", &map[i][j]);}memset(dp, -1, sizeof(dp));//初始化出口下面一格为1for (i = 0; i < 15; i++)dp[n][m - 1][i][k] = 1;printf("%d\n", dfs(0, 0, -1, 0));return 0;
}我就解释一下
if (dp[i][j][max+1][num] != -1)return dp[i][j][max+1][num];为什么是max+1， 因为数据中宝贝的价值可能为0，所以在传值的时候我们不能用0来初始化当前的最大值但是用-1的话数组下标会越界，所以我们干脆所有max都加1，其实表示的还是原来值的方法数，只不过都往后推了一个这篇关于蓝桥杯c/c++预选赛 地宫取宝的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
