题目描述
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)的宝物。例如,在非终点的情况下,处理不拿和拿的情况:
- 不拿的话,移动时cnt还是0,max_val是0。
- 拿的话,需要满足grid[0][0] >0(因为max_val初始是0,而宝物价值已加1),所以如果起点的宝物价值是0(处理后的1),则大于0,可以拿。
这样,初始调用只需要一次,即dfs(0,0,0,0),因为递归函数内部处理了是否拿取当前格子的宝物。
但是,这样的处理是否正确?例如,小明在起点处选择不拿,那么后面的移动是否还能拿其他宝物?是的,因为max_val仍然是0,后面遇到比0大的宝物可以拿。
但如果小明在起点处选择拿,那么cnt变为1,max_val变为grid[0][0]。
这样,递归函数的设计是正确的。
现在,关于记忆化数组的初始化,需要将所有值初始化为-1,表示未访问过。在C++中,可以用memset或fill函数进行初始化。
此外,考虑到宝物的价值已经被加1处理,max_val的取值范围是0到13(因为原来的Ci最大是12,加1后最大是13)。
因此,记忆化数组的维度应该是n x m x (k+1) x 14。例如,在C++中,可以定义为:
int memo[50][50][13][14]; // n,m <=50; k<=12; max_val <=13.
但动态定义可能更灵活。或者,使用vector来定义四维数组。
例如:
vector<vector<vector<vector<int>>>> memo(n,
vector<vector<vector<int>>>(m,
vector<vector<int>>(k+1,
vector<int>(14, -1)
)
)
);
这样,在每次测试用例时,重新初始化memo数组为-1。
综上,结合以上思路,可以编写出DFS+记忆化的代码。但需要注意,这种方法在n和m较大时,可能会超时,因为状态数是50 * 50 * 12 * 14=420,000,每个状态需要计算多次,但可能还是可以接受的,尤其是在题目给定的时间限制下。
最后,需要将输入的宝物价值加1,并将初始max_val设为0(表示未拿任何宝物时的状态)。