首页 > 代码库 > 蓝桥杯 地宫寻宝 DFS 动态规划
蓝桥杯 地宫寻宝 DFS 动态规划
#define _CRT_SECURE_NO_WARNINGS#include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring> #include <queue>using namespace std;const int maxn = 100;const long long INF = 1000000007; //用来取余 int maze[maxn][maxn];int d[52][52][14][14]; //行,列,k个数,valueint n, m, k; //[n,m], k件宝贝long long ans; //方案数 int dfs(int r, int c, int sum, int Max); //当前位置 void input();void solve();void input(){ memset(d, -1, sizeof(d)); scanf("%d%d%d", &n, &m, &k); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%d", &maze[i][j]); } }}int dfs(int r, int c, int sum, int Max){ if (d[r][c][sum][Max + 1] != -1) { //已经遍历完, 并设置了结果 return d[r][c][sum][Max + 1]; //返回结果 } int t = 0; if (r == n - 1 && c == m - 1) { //到达入口 if (maze[r][c] > Max) { //可以再拿一个宝物 if (sum == k || sum == k - 1) //如果已经到了 k 或是 k-1,方案++ t++; } else if (sum == k) { //不能拿时候,则此时就需要为k, 方案++ t++; } return d[r][c][sum][Max + 1] = t; //更新方案数 } if (r + 1 < n) { if (maze[r][c] > Max) { //可以拿 t += dfs(r + 1, c, sum + 1, maze[r][c]); //选择拿 t %= INF; t += dfs(r + 1, c, sum, Max); //选择不拿 t %= INF; } else { t += dfs(r + 1, c, sum, Max); //不可以拿 t %= INF; } } if (c + 1 < m) { if (maze[r][c] > Max) { t += dfs(r, c + 1, sum + 1, maze[r][c]); t %= INF; t += dfs(r, c + 1, sum, Max); t %= INF; } else { t += dfs(r, c + 1, sum, Max); t %= INF; } } d[r][c][sum][Max + 1] = t; //将方案数 保存在Max + 1 处 return d[r][c][sum][Max + 1]; //返回方案数 }void solve(){ input(); ans = dfs(0, 0, 0, -1); cout << ans << endl;}int main(){ solve(); return 0;}
//不太熟悉动态规划的题目.................,参考了网上解法,回头看看这类题目.......
蓝桥杯 地宫寻宝 DFS 动态规划
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。