蓝桥杯2014年第五届真题-地宫取宝 记忆化搜索

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
#define ll long long
// 定义全局变量n, m, k分别表示行数、列数和步数限制
ll n, m, k;
// 定义二维数组a，用于存储输入的矩阵
ll a[60][60];
// 定义四维数组kkk，用于记忆化搜索，避免重复计算
ll kkk[60][60][15][15];
ll dfs(ll x, ll y, ll z, ll kk) {
    // 如果当前状态已经计算过，直接返回结果
    if (kkk[x][y][z][kk] != -1) {
        return kkk[x][y][z][kk];
    }
    // 初始化路径数量为0
    ll sum = 0;
    // 如果超出边界或者步数超过限制，返回0
    if (x > n || y > m || kk > k) {
        return 0;
    }
    // 如果到达终点且步数符合要求，返回1
    if (x == n && y == m && (kk == k || (kk == k - 1 && a[x][y] > z))) {
        return 1;
    }
    // 如果当前位置的值大于上一个位置的值，取宝贝尝试向下或向右移动
    if (a[x][y] > z) {
        sum += dfs(x, y + 1, a[x][y], kk + 1); // 向右移动
        sum += dfs(x + 1, y, a[x][y], kk + 1); // 向下移动
    }
    // 不取宝贝尝试向下或向右移动
    sum += dfs(x + 1, y, z, kk); // 向下移动
    sum += dfs(x, y + 1, z, kk); // 向右移动

    // 将计算结果存入记忆化数组中
    kkk[x][y][z][kk] = sum;

    // 返回结果并取模，防止溢出
    return sum % 1000000007;
}

int main() {
    // 读取输入的行数、列数和步数限制
    cin >> n >> m >> k;
    // 初始化记忆化数组为-1，表示未计算过的状态
    memset(kkk, -1, sizeof(kkk));
    // 读取矩阵数据
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    // 输出从起点(1,1)开始满足条件的路径数量
    cout << dfs(1, 1, -1, 0) << endl;
    return 0;
}