DFS搜索问题 地宫取宝 蓝桥杯 X 国王有一个地宫宝库。是 n x m 个格子的矩阵。

Question

这个DFS搜索有问题吗？为什么第三个数据就过不了？

#include<stdio.h>
#include<string.h>

#define N 1000000007

int p[50][50];
int d[50][50][13][13];
int n, m, k;

int DFS(int x,int y,int now,int nowmax){
    if (d[x][y][now][nowmax] != -1)return d[x][y][now][nowmax];

    int way=0;

    if (x == n-1&&y == m-1){
        if (now == k - 1 && p[x][y] > nowmax)
            way++;
        if (now == k)
            way++;
        return d[x][y][now][nowmax] = way;
    }

    if (x + 1 < n)
    {
        if (p[x][y] > nowmax){
            way+= DFS(x + 1, y, now+1, p[x][y]);
            way %= N;
        }
        way += DFS(x + 1, y, now, nowmax);
        way %= N;
    }
    if (y + 1 < m)
    {
        if (p[x][y] > nowmax){
            way += DFS(x, y + 1, now + 1, p[x][y]);
            way %= N;
        }
        way += DFS(x, y + 1, now, nowmax);
        way %= N;
    }

    d[x][y][now][nowmax]=way;
    return way;


}

int main(){
    scanf_s("%d %d %d", &n, &m, &k);
    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        scanf_s("%d", &p[i][j]);
    memset(d, -1, sizeof(d));

    int sum = DFS(0,0,0,0);

    printf("%d\n", sum);

    return 0;
}

可为什么这个就过的了？这两个有区别吗？

#include <iostream>  
#include <cmath>  
#include <cstdio>  
#include <cstring>  
using namespace std;

#define eps 10e-10  
#define N 1000000007  

int ans;
int d[51][51][13][14];
int p[51][51];
int n, m, k;

int dfs(int x, int y, int num, int maxvalue){
    if (d[x][y][num][maxvalue + 1] != -1){
        return d[x][y][num][maxvalue + 1];
    }


    int t = 0;

    if (x == n - 1 && y == m - 1){
        if (p[x][y] > maxvalue){
            if (num == k || num == k - 1)
                t++;
        }
        else if (num == k){
            t++;
        }
        return d[x][y][num][maxvalue + 1] = t;
    }

    if (x + 1 < n){
        if (p[x][y] > maxvalue){
            t += dfs(x + 1, y, num + 1, p[x][y]);
            t %= N;
            t += dfs(x + 1, y, num, maxvalue);
            t %= N;
        }
        else {
            t += dfs(x + 1, y, num, maxvalue);
            t %= N;
        }
    }

    if (y + 1 < m){
        if (p[x][y] > maxvalue){
            t += dfs(x, y + 1, num + 1, p[x][y]);
            t %= N;
            t += dfs(x, y + 1, num, maxvalue);
            t %= N;
        }
        else {
            t += dfs(x, y + 1, num, maxvalue);
            t %= N;
        }
    }

    d[x][y][num][maxvalue + 1] = t;
    return d[x][y][num][maxvalue + 1];
}

int main(){
    while (cin >> n >> m >> k){
        for (int i = 0; i < n; ++i){
            for (int j = 0; j < m; ++j)
                cin >> p[i][j];
        }
        memset(d, -1, sizeof(d));
        d[0][0][0][0] = dfs(0, 0, 0, -1);
        cout << d[0][0][0][0] << endl;
    }
    return 0;
}

Answer 1

您提供的两个代码都是地宫取宝问题的 DFS 解法，但是实现方法不同，第一个代码使用的是四维数组 d，而第二个代码使用的是三维数组 d。具体来说，第一个代码中的 d 数组表示从位置 (x,y) 出发，当前已经取到了 num 个宝物，最大宝物价值为 maxvalue 的方案数，而第二个代码中的 d 数组表示从位置 (x,y) 出发，当前已经取到了 num 个宝物，上一个已经取的宝物的价值为 maxvalue 的方案数。

在第一个代码中，由于采用了四维数组，导致空间复杂度很高，而且数组的第四维没有必要，因为 maxvalue 最大只有 10^6，因此可以通过将其减去 1 后存储在三维数组中来节约空间。另外，在第一个代码中，搜索的顺序是先向下搜索，再向右搜索，这会导致某些状态被重复计算。改成先向右搜索，再向下搜索可以避免这个问题。

第二个代码的实现和第一个代码相比，空间复杂度更低，而且搜索顺序也是先向右搜索，再向下搜索，因此可以避免重复计算。同时，第二个代码中的 if 判断条件也更加简洁和清晰。

综上所述，第二个代码更优秀一些，可以通过第三个数据。