首页 > 代码库 > 蓝桥杯 地宫寻宝 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 动态规划