【求助】记忆化搜索，样例过不了

聪明的猪 @ 2020-09-19 22:05:12

#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

int _skiResort[105][105];
int _ans[105][105];

int dfs(int, int, int, int);

int main(void)
{
    int c = 0, r = 0, res = -1;
    memset(_ans, 0, sizeof (_ans));
    memset(_skiResort, 0, sizeof (_skiResort));

    scanf("%d %d", &r, &c);

    for (int i = 1; i < r + 1; i++)
    {
        for (int j = 1; j < c + 1; j++)
        {
            scanf("%d", &_skiResort[i][j]);
        }
    }

    for (int i = 1; i < r + 1; i++)
    {
        for (int j = 1; j < c + 1; j++)
        {
            res = max(res, dfs(c, r, i, j));
        }
    }

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

    return 0;
}

int dfs(int m, int n, int x, int y)
{
    if (_ans[x][y])
    {
        return _ans[x][y];
    }

    int dx = 0, dy = 0;
    _ans[x][y] = 1;

    dx = x;
    dy = y + 1;
    if (0 < dx && 0 < dy && dx < n + 1 && dy < m + 1 && _skiResort[dx][dy] < _skiResort[x][y])
    {
        dfs(m, n, dx, dy);
        _ans[x][y] = max(_ans[x][y], _ans[dx][dy]);
    }

    dx = x - 1;
    dy = y;
    if (0 < dx && 0 < dy && dx < n + 1 && dy < m + 1 && _skiResort[dx][dy] < _skiResort[x][y])
    {
        dfs(m, n, dx, dy);
        _ans[x][y] = max(_ans[x][y], _ans[dx][dy]);
    }

    dx = x;
    dy = y - 1;
    if (0 < dx && 0 < dy && dx < n + 1 && dy < m + 1 && _skiResort[dx][dy] < _skiResort[x][y])
    {
        dfs(m, n, dx, dy);
        _ans[x][y] = max(_ans[x][y], _ans[dx][dy]);
    }

    dx = x + 1;
    dy = y;
    if (0 < dx && 0 < dy && dx < n + 1 && dy < m + 1 && _skiResort[dx][dy] < _skiResort[x][y])
    {
        dfs(m, n, dx, dy);
        _ans[x][y] = max(_ans[x][y], _ans[dx][dy]);
    }

    return _ans[x][y];
}

by 聪明的猪 @ 2020-09-19 22:11:07

看了下题解，似乎把判断那改成一个for循环会更易读一些[汗]

by peterwuyihong @ 2020-09-19 22:12:58

#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

int _skiResort[105][105];
int _ans[105][105];

int dfs(int, int, int, int);

int main(void)
{
    int c = 0, r = 0, res = -1;
    memset(_ans, 0, sizeof (_ans));
    memset(_skiResort, 0, sizeof (_skiResort));

    scanf("%d %d", &r, &c);

    for (int i = 1; i < r + 1; i++)
    {
        for (int j = 1; j < c + 1; j++)
        {
            scanf("%d", &_skiResort[i][j]);
        }
    }

    for (int i = 1; i < r + 1; i++)
    {
        for (int j = 1; j < c + 1; j++)
        {
            res = max(res, dfs(c, r, i, j));
        }
    }

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

    return 0;
}

int dfs(int m, int n, int x, int y)
{
    if (_ans[x][y])
    {
        return _ans[x][y];
    }

    int dx = 0, dy = 0;
    _ans[x][y] = 1;

    dx = x;
    dy = y + 1;
    if (0 < dx && 0 < dy && dx < n + 1 && dy < m + 1 && _skiResort[dx][dy] < _skiResort[x][y])
    {
        _ans[x][y] = max(_ans[x][y], dfs(m, n, dx, dy)+1);
    }

    dx = x - 1;
    dy = y;
    if (0 < dx && 0 < dy && dx < n + 1 && dy < m + 1 && _skiResort[dx][dy] < _skiResort[x][y])
    {
        _ans[x][y] = max(_ans[x][y], dfs(m, n, dx, dy)+1);
    }

    dx = x;
    dy = y - 1;
    if (0 < dx && 0 < dy && dx < n + 1 && dy < m + 1 && _skiResort[dx][dy] < _skiResort[x][y])
    {
        _ans[x][y] = max(_ans[x][y], dfs(m, n, dx, dy)+1);
    }

    dx = x + 1;
    dy = y;
    if (0 < dx && 0 < dy && dx < n + 1 && dy < m + 1 && _skiResort[dx][dy] < _skiResort[x][y])
    {

        _ans[x][y] = max(_ans[x][y], dfs(m, n, dx, dy)+1);
    }

    return _ans[x][y];
}

参考一下这个，记搜的精髓你莫得领悟

by peterwuyihong @ 2020-09-19 22:13:31

这用户名是smg啊

by peterwuyihong @ 2020-09-19 22:13:52

@聪明的猪

by 聪明的猪 @ 2020-09-22 08:55:31

@吴亦泓 多谢dalao指点！