每日一题之地宫取宝

题目描述

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

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

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

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

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

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

输入描述

输入一行 3 个整数，用空格分开：n,m,k (1≤n,m≤50,1≤k≤12)。

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

输出描述

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

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;// 全局常量定义
const int MOD = 1e9 + 7;          // 模数取10^9+7
const int MAX_K = 13;             // 最大可取宝物数+1（k≤12）
const int MAX_VAL = 14;           // 价值上限（原价值0-12，+1后1-13）
int n, m, k;                      // 地宫行列数和目标宝物数
vector<vector<int>> grid;          // 地宫宝物价值矩阵// 四维记忆数组：memo[i][j][cnt][max_val] 表示在(i,j)位置，
// 已取cnt个宝物且当前最大价值为max_val的状态方案数[3](@ref)
int memo[50][50][13][14];         // 按题目最大范围50x50x12x14// 深度优先搜索函数
// 参数：当前位置(i,j)，已收集宝物数cnt，当前最大价值max_val
// 返回：从当前位置到终点的合法路径数[8](@ref)
int dfs(int i, int j, int cnt, int max_val) {// 终点判断（右下角格子）if (i == n-1 && j == m-1) {int cases = 0;// 情况1：已收集k件且不取终点[6](@ref)if (cnt == k) cases++; // 情况2：已收集k-1件且可取终点宝物if (cnt == k-1 && grid[i][j] > max_val) cases++;return cases % MOD;}// 记忆化查询（已计算过的状态直接返回）if (memo[i][j][cnt][max_val] != -1) return memo[i][j][cnt][max_val];int res = 0;// 不取当前格子的两种情况（向右/向下移动）if (j+1 < m)  // 向右移动合法时res = (res + dfs(i, j+1, cnt, max_val)) % MOD;if (i+1 < n)  // 向下移动合法时res = (res + dfs(i+1, j, cnt, max_val)) % MOD;// 尝试取当前格子的两种情况（需满足价值递增条件）if (grid[i][j] > max_val && cnt < k) {int new_cnt = cnt + 1;int new_max = grid[i][j];// 更新状态后继续递归if (j+1 < m) res = (res + dfs(i, j+1, new_cnt, new_max)) % MOD;if (i+1 < n)res = (res + dfs(i+1, j, new_cnt, new_max)) % MOD;}// 记录当前状态并返回结果return memo[i][j][cnt][max_val] = res;
}int main() {// 输入处理cin >> n >> m >> k;grid.resize(n, vector<int>(m));for (int i = 0; i < n; ++i)for (int j = 0; j < m; ++j) {cin >> grid[i][j];grid[i][j]++;  // 价值+1处理（避免0值冲突）[3](@ref)}// 初始化记忆数组为-1（表示未计算状态）memset(memo, -1, sizeof(memo));// 从起点(0,0)开始，初始状态未取任何宝物（cnt=0，max_val=0）cout << dfs(0, 0, 0, 0) << endl;return 0;
}

DFS的基本思路应该是：从起点(0,0)开始，每次选择向右或向下移动，同时记录当前已经收集的宝物数量以及当前的最大价值。当到达终点时，如果收集的宝物数量正好是k，则计数加一。

不过，这样的纯递归会有很多重复计算，导致效率极低。因此，通常会使用记忆化搜索（即DFS+备忘录）来优化。记忆化搜索需要记录状态，包括当前位置(i,j)、已收集的数量cnt、当前最大价值max_val。这样可以将已经计算过的状态保存下来，避免重复计算。

在动态规划中，状态是四维的：位置(i,j)、数量c、最大价值v。同样，在记忆化DFS中，也需要同样的状态参数。因此，记忆化数组应该是四维的，或者至少包含这四个关键状态。

另外，需要注意的是，宝物的价值可能为0，但为了处理初始状态（没有拿任何宝物时，max_val可以设为-1或者0，但需要统一处理）。在之前的动态规划解法中，宝物价值被加1，以避免0的问题，可能在这里也需要类似的处理。

所以，DFS的步骤大概是这样的：

参数：当前位置(i,j)，已拿的数量cnt，当前最大价值max_val。
终止条件：到达终点(n-1,m-1)，如果此时cnt等于k，返回1，否则返回0。
递归转移：向右和向下移动。
在每个位置，有两种选择：拿当前宝物或不拿。
a. 如果拿，需要满足当前宝物的价值大于max_val，并且cnt < k。
b. 不拿的话，直接转移到下一个位置。
使用记忆化数组来存储已经计算过的状态，避免重复计算。

但是，直接这样实现可能会有问题，比如当max_val的值范围较大时，数组会很大。不过题目中宝物的价值最多是12，加上1之后是13，所以max_val的可能取值是0到13（初始状态设为-1，但处理后变为0）。

另外，需要处理数组越界的问题，即i和j不能超过n-1和m-1。

现在，我需要考虑如何初始化记忆化数组。由于n和m最多是50，k是12，max_val是0到13，所以记忆化数组的维度是50x50x13x14，这在C++中应该是可行的，但需要注意内存使用。不过，题目中的结果需要对1e9+7取模，所以用int或long long存储。

接下来，编写代码的大致结构：

定义dfs函数，参数是i,j,cnt,max_val。
如果到达终点，检查cnt是否等于k。
对于当前位置的宝物，判断是否拿取。
递归向右和向下移动，并将结果相加。
使用记忆化数组保存结果，避免重复计算。

另外，处理拿取宝物的情况时，如果当前宝物的价值大于max_val，并且cnt+1 <=k，则可以拿取，此时新的max_val变为当前宝物的价值，cnt+1。

需要注意的是，初始状态时，max_val可能是-1（如果还没有拿任何宝物），或者根据处理后的值进行调整。例如，在动态规划中，宝物价值被加1，所以初始max_val可以是0，这样当第一次拿的宝物价值为0（处理后为1）时，可以正确比较。

因此，在DFS中，宝物价值也应该加1，这样初始的max_val可以设为0（表示没有拿任何宝物），当第一次拿的时候，只要当前宝物的价值（已加1）>0即可。

所以，在代码中，输入的宝物价值需要先加1处理，类似于动态规划的做法。

现在，综合这些思路，可以开始编写代码框架：

定义memo[i][j][cnt][max_val]，表示在(i,j)位置，已经拿了cnt个宝物，当前最大价值是max_val时的路径数。

递归函数的大致逻辑：

int dfs(int i, int j, int cnt, int max_val) {
if (i == n-1 && j == m-1) {
return cnt == k ? 1 : 0;
}
if (memo[i][j][cnt][max_val] != -1) {
return memo[i][j][cnt][max_val];
}
int res = 0;
// 向右走
if (j+1 < m) {
// 不拿下一个位置的宝物
res += dfs(i, j+1, cnt, max_val);
res %= MOD;
// 拿下一个位置的宝物，前提是满足条件
int next_val = grid[i][j+1];
if (cnt < k && next_val > max_val) {
res += dfs(i, j+1, cnt+1, next_val);
res %= MOD;
}
}
// 向下走
if (i+1 < n) {
// 不拿
res += dfs(i+1, j, cnt, max_val);
res %= MOD;
// 拿
int next_val = grid[i+1][j];
if (cnt < k && next_val > max_val) {
res += dfs(i+1, j, cnt+1, next_val);
res %= MOD;
}
}
memo[i][j][cnt][max_val] = res;
return res;
}

不过，这样的写法可能有问题，因为当移动到下一个位置时，处理的是下一个位置的宝物。例如，当向右走到(i,j+1)时，是否拿的是grid[i][j+1]的宝物。所以，在当前位置处理的是当前位置的宝物，或者下一个位置的？

这里可能存在逻辑错误。正确的做法应该是：当移动到下一个位置（比如向右走到(i,j+1)），此时处理的是该位置的宝物。因此，在到达(i,j)时，是否拿取的是grid[i][j]的宝物？

或者，可能在递归时处理的是当前所在位置的宝物。例如，小明在移动到(i,j)时，可以选择是否拿取这里的宝物，然后继续移动。

所以，可能需要重新调整递归的逻辑：当小明到达(i,j)时，处理该位置的宝物，然后移动到右边或下边。

这样，初始调用应该是从起点(0,0)开始，处理是否拿取起点处的宝物，然后递归到右边或下边。

因此，递归函数的结构可能需要调整：

在到达(i,j)时，有两种情况：已经拿了这里的宝物，或者没有拿。因此，在递归时，需要考虑在当前位置是否拿取宝物，然后处理移动。

这可能更符合问题的逻辑。例如，小明走到(i,j)时，可以选择是否拿这里的宝物（如果满足条件），然后继续向右或向下走。

因此，递归函数的结构可能需要重新设计：

函数参数包括当前位置(i,j)，已经拿的数量cnt，当前最大价值max_val。当处理当前位置时，可以选择拿或者不拿，然后移动。

例如，在函数内部：

处理当前位置是否拿取宝物。
a. 如果之前没有拿过这里的宝物，现在可以选择拿，前提是当前宝物的价值大于max_val，并且cnt <k。
b. 或者选择不拿，不管之前是否拿过。

但这样的话，可能需要记录是否已经在该位置拿过宝物，但题目中每个格子只能经过一次，所以每个格子只能处理一次是否拿取，不能在之后返回时再拿。

因此，正确的处理流程是：当小明第一次到达(i,j)时，决定是否拿取该宝物，然后继续移动，不能再回来拿。

因此，递归函数的结构应该是这样的：

当到达(i,j)时，首先处理是否拿取该位置的宝物，然后向右或向下移动。

因此，递归函数的参数应该包括当前位置(i,j)，已拿数量cnt，当前最大价值max_val。在到达该位置时，处理拿或者不拿的选择，然后递归到下一个位置。

这样，初始调用应该是在起点(0,0)，此时可以选择拿或者不拿起点的宝物，然后递归到右边或下边。

因此，递归函数的逻辑应该调整为：

在(i,j)位置时：

如果不拿这里的宝物，那么保持cnt和max_val不变，向右或向下移动。
如果拿这里的宝物，前提是grid[i][j] > max_val，并且cnt+1 <=k，那么更新cnt和max_val，然后移动。

这样，递归的处理应该是在每个位置处理拿或不拿的选择，然后再移动。而不是在移动之后处理下一个位置的宝物。

这可能更正确，因为小明在走到某个格子时，才决定是否拿该格子的宝物，而不是在移动前处理下一个位置的宝物。

所以，正确的递归步骤应该是：

到达(i,j)时：

先处理是否拿这个格子的宝物：
a. 不拿：此时状态保持不变，继续向右或向下移动。
b. 拿：如果当前宝物的价值大于max_val，并且cnt <k，那么cnt+1，max_val更新为当前宝物的价值，然后移动。
移动到右边或下边，前提是不越界。

同时，需要考虑到达终点时的处理：必须在终点处完成所有选择，即是否拿终点的宝物，使得最终数量正好是k。

因此，递归函数的终止条件是当i ==n-1且j ==m-1时，处理完该位置的拿或不拿后，检查cnt是否等于k。

这样，整个递归的结构需要调整。

例如：

int dfs(int i, int j, int cnt, int max_val) {
// 处理当前格子是否拿取
if (i == n-1 && j == m-1) {
// 到达终点，检查当前处理后的cnt是否等于k
// 这里需要处理是否拿终点处的宝物
int ans =0;
// 不拿的情况
if (cnt ==k) {
ans +=1;
}
// 拿的情况，如果满足条件
if (cnt <k && grid[i][j] > max_val && cnt+1 ==k) {
ans +=1;
}
return ans % MOD;
}
if (memo[i][j][cnt][max_val] != -1) {
return memo[i][j][cnt][max_val];
}
int res =0;
// 处理当前格子是否拿取
// 选择不拿
// 然后移动
if (j+1 <m) { // 向右
res += dfs(i, j+1, cnt, max_val);
res %= MOD;
}
if (i+1 <n) { // 向下
res += dfs(i, j+1, cnt, max_val); // 应该是i+1, j？
res %= MOD;
}
// 这里可能写错了，应该是i+1,j?
// 修正：
if (i+1 <n) {
res += dfs(i+1, j, cnt, max_val);
res %= MOD;
}

// 选择拿当前格子宝物
if (grid[i][j] > max_val && cnt <k) {int new_cnt = cnt +1;int new_max = grid[i][j];// 移动if (j+1 <m) {res += dfs(i, j+1, new_cnt, new_max);res %= MOD;}if (i+1 <n) {res += dfs(i+1, j, new_cnt, new_max);res %= MOD;}
}memo[i][j][cnt][max_val] = res;
return res;

但这样处理的话，在到达每个位置时，会有两种选择：拿或者不拿当前宝物，然后继续移动。这样，在递归中，每个位置的处理分为两种情况，导致状态数翻倍。但根据题目要求，小明在走到某个格子时，可以选择拿或者不拿，但一旦离开该格子就不能再回来拿。

因此，这样的结构是正确的。而初始调用应该是从起点开始，处理拿或不拿起点的宝物，然后递归。

但此时，初始调用应该如何？例如，小明在起点(0,0)处，可以选择拿或不拿：

所以，最终的答案应该是：

dfs(0,0,0,0) // 不拿起点宝物的情况，加上 dfs(0,0,1, grid[0][0]) // 拿起点宝物的情况？

或者，在dfs函数内部处理是否拿取当前宝物？

这需要重新设计递归函数，使其处理的是在当前位置的拿或不拿的选择，而不是在移动之后处理下一个位置的选择。

这可能更合理。例如，在函数中，当处理到(i,j)时，首先处理是否拿取这里的宝物，然后递归到右边和下面的格子。

此时，递归函数的参数是当前位置(i,j)，已经拿的数量cnt，当前最大价值max_val，表示的是到达该位置时已经做的选择（是否拿取该位置的宝物之前的状态）。

例如，当小明到达(i,j)时，还没有决定是否拿这里的宝物，所以函数内部处理是否拿取，然后移动。

或者，参数表示的是已经处理完该位置的拿取状态，即到达(i,j)时，已经完成了拿或不拿的选择，此时的状态是cnt和max_val。然后，递归到右边和下面的格子。

这可能需要将递归函数分为两种情况：在处理完当前位置的选择后，移动。

例如，函数dfs(i,j,cnt,max_val)表示的是小明在(i,j)位置，已经处理过是否拿这里的宝物，现在要移动到下一个格子。这可能不太对。

或者，另一种设计方式是：当小明移动到(i,j)时，处理是否拿这里的宝物，然后继续移动。因此，函数参数表示的是到达(i,j)时的状态（比如，还没有拿这里的宝物），然后在函数内部处理拿或者不拿的选择，再移动。

这可能会更复杂，因为每个位置的处理分为两种情况：拿或者不拿。

或者，将函数参数设计为到达(i,j)时的状态，包括是否已经拿取了该位置的宝物。但这会增加状态参数，例如一个布尔标志，表示是否已经处理过该位置的拿取。这会导致状态数进一步增加，可能不可行。

因此，可能需要重新考虑递归函数的设计，使其在到达(i,j)时，处理拿或不拿的选择，然后移动。

正确的做法应该是：小明到达(i,j)格子，此时可以决定是否拿该格子的宝物，前提是满足条件。然后，无论是否拿取，都必须向右或向下移动，直到终点。

因此，递归函数的参数应该是在到达(i,j)时的状态（即已经拿的数目cnt和当前最大max_val），然后处理是否拿取该格子的宝物，然后移动到下一个格子。

例如：

在函数dfs(i,j,cnt,max_val)中：

处理是否拿取当前格子(i,j)的宝物。
a. 不拿：此时保持cnt和max_val不变，继续向右或向下移动。
b. 拿：如果当前宝物的价值大于max_val，并且cnt+1 <=k，则更新cnt和max_val，再移动。

需要注意的是，每个格子只能处理一次拿取决策，即小明在第一次到达该格子时决定是否拿取，之后不能返回。

因此，递归函数的正确逻辑应该是：

当小明到达(i,j)时，处理该格子的拿取选择，然后移动。

所以，递归函数的调用应该是在处理完当前格子之后，移动到下一个格子。例如：

int dfs(int i, int j, int cnt, int max_val) {
// 如果已经处理过这个状态，直接返回
if (memo[i][j][cnt][max_val] != -1) {
return memo[i][j][cnt][max_val];
}

// 当前格子是否处理拿取？
// 不拿的情况：此时不改变cnt和max_val，直接移动
// 拿的情况：如果满足条件，更新cnt和max_val，然后移动int res =0;// 先处理不拿当前格子的情况，直接移动
// 但需要移动到右边或下边
// 但此时需要移动到下一个格子，所以在移动之后处理下一个格子的选择？// 不，这样可能不正确，因为当前格子的处理应该是在该格子停留时进行的选择，而不是移动后的格子。// 正确的做法是，在当前位置处理是否拿取，然后移动到下一个位置时处理下一个位置的选择。// 因此，当前函数处理的是到达(i,j)后的选择，然后移动到下一个位置。// 因此，需要先处理是否拿取当前格子，然后递归到下一个位置。// 所以，处理当前格子的拿取选择：// 情况一：不拿当前格子
int new_cnt = cnt;
int new_max = max_val;
// 此时，移动到右边或下边，递归处理下一个格子
if (j < m-1) { // 可以向右res += dfs(i, j+1, new_cnt, new_max);res %= MOD;
}
if (i < n-1) { // 可以向下res += dfs(i+1, j, new_cnt, new_max);res %= MOD;
}// 情况二：拿当前格子，如果满足条件
if (grid[i][j] > new_max && new_cnt <k) {int take_cnt = new_cnt +1;int take_max = grid[i][j];// 移动后处理下一个格子if (j < m-1) {res += dfs(i, j+1, take_cnt, take_max);res %= MOD;}if (i <n-1) {res += dfs(i+1, j, take_cnt, take_max);res %= MOD;}
}// 如果当前是终点，需要处理特殊情况？
if (i ==n-1 && j ==m-1) {// 在终点处，是否已经处理了拿或不拿的情况？// 此时，如果在终点处不拿，且cnt ==k，则res +=1// 如果在终点处拿，并且满足条件，且 cnt+1 ==k，则res +=1// 所以，在终点处，两种情况都要考虑// 但根据上面的处理，当到达终点时，移动操作会越界，所以需要在此时检查是否到达终点// 上面的处理可能无法覆盖终点的情况，所以需要单独处理终点处的情况// 例如，当i,j是终点时，移动的话j+1或i+1会越界，所以此时无法继续移动，递归终止// 所以，当到达终点时，是否拿取该格子的宝物，然后判断是否满足条件int current_res =0;// 不拿的情况：如果已经处理了不拿，此时移动会导致越界，所以在这里处理if (i ==n-1 && j ==m-1) {if (new_cnt ==k) {current_res +=1;}}// 拿的情况：if (grid[i][j] > new_max && new_cnt <k) {if (new_cnt +1 ==k) {current_res +=1;}}res += current_res;res %= MOD;
}memo[i][j][cnt][max_val] = res;
return res;

但这样的处理可能比较复杂，尤其是在终点处的判断。因为当i,j是终点时，j+1和i+1都会越界，所以在移动到下个位置时会直接返回0，而真正的判断需要在处理当前格子时进行。

因此，在递归函数中，当处理到终点(i,j)时，无论是选择拿还是不拿，都需要立即判断是否满足条件，并返回相应的结果，而不是继续移动。

因此，递归函数的终止条件应该是在处理完当前格子（终点）后，检查是否满足k件宝物。

因此，正确的递归终止条件应该是在处理当前位置是否为终点时，无论是拿还是不拿，都要计算可能的情况。

这可能需要在递归函数的开始部分处理：

int dfs(int i, int j, int cnt, int max_val) {
// 检查是否已经缓存
if (memo[i][j][cnt][max_val] != -1) {
return memo[i][j][cnt][max_val];
}

// 处理终点情况
if (i == n-1 && j == m-1) {int ans =0;// 不拿该格子的情况if (cnt ==k) {ans +=1;}// 拿该格子的情况if (cnt <k && grid[i][j] > max_val && cnt+1 ==k) {ans +=1;}ans %= MOD;memo[i][j][cnt][max_val] = ans;return ans;
}// 非终点情况，处理拿或不拿的选择
int res =0;// 不拿当前格子，直接移动
if (j+1 <m) {res += dfs(i, j+1, cnt, max_val);res %= MOD;
}
if (i+1 <n) {res += dfs(i+1, j, cnt, max_val);res %= MOD;
}// 拿当前格子，如果满足条件
if (grid[i][j] > max_val && cnt <k) {int new_cnt = cnt+1;int new_max = grid[i][j];if (j+1 <m) {res += dfs(i, j+1, new_cnt, new_max);res %= MOD;}if (i+1 <n) {res += dfs(i+1, j, new_cnt, new_max);res %= MOD;}
}memo[i][j][cnt][max_val] = res;
return res;

这样，当到达终点时，处理是否拿取该位置的宝物，并判断是否满足cnt==k或者cnt+1 ==k（如果是拿的情况）。

这样，递归函数的初始调用应该是：

int ans = dfs(0, 0, 0, 0);

但是，这样的话，在起点处，小明可以选择不拿或者拿。但根据上述代码，在起点处的处理会被自动处理吗？

是的，因为在递归函数中，当调用dfs(0,0,0,0)时，会处理是否拿取(0,0)的宝物。例如，在非终点的情况下，处理不拿和拿的情况：