记忆化搜索问题，怎么得了80分?

Dreamerlee✅ @ 2021-04-06 17:26:45

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int r, c, a[110][110], b[110][110], sum, tns = -0x7777777,ans=-0x7777777;
int dx[5] = { 0,1,-1,0,0 };
int dy[5] = { 0,0,0,-1,1 };
int dfs(int x, int y, int t)//t代表步数
{
    if (b[x][y])
        return t + b[x][y];//步数加上之前记忆的数组的值
    b[x][y] = 1;//既然这是一个从未走过的点那么现在来到该点至少都会使其步数为1 
    for (int i = 1; i <= 4; i++)
    {
        int px = x + dx[i];
        int py = y + dy[i];
        if (px >= 1 && px <= r && py >= 1 && py <= c)//不越界
        {
            if (a[px][py] < a[x][y])//滑雪只能滑向高度小的坐标
            {
                sum = max(ans,dfs(px, py, t + 1));//步数t每次加+1,每次取最大的给sum
                b[x][y] = max(b[x][y], sum);//记录最大的步数
            }
        }
    }
    return b[x][y];
}
int main()
{
    cin >> r >> c;
    for (int i = 1; i <= r; i++)
    {
        for (int j = 1; j <= c; j++)
            cin >> a[i][j];
    }
    for (int i = 1; i <= r; i++)
    {
        for (int j = 1; j <= c; j++)
            dfs(i, j, 0);//步数一上来从0开始
    }
    for (int i = 1; i <= r; i++)
    {
        for (int j = 1; j <= c; j++)
        {
            tns = max(tns, b[i][j]);//找最大步数
        }
    }
    cout << tns;
    return 0;
}
```cpp

by metaphysis @ 2021-04-06 19:54:09

@Dreamerlee✅

确实是逻辑没有理清楚就开始编码了，所以容易出问题。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int r, c, a[110][110], b[110][110], sum, tns = -0x7777777,ans=-0x7777777;
int dx[5] = { 0,1,-1,0,0 };
int dy[5] = { 0,0,0,-1,1 };
int dfs(int x, int y)//t代表步数
{
    if (b[x][y]) 
        //return t + b[x][y];//步数加上之前记忆的数组的值
        return b[x][y];

    b[x][y] = 1;//既然这是一个从未走过的点那么现在来到该点至少都会使其步数为1 
    for (int i = 1; i <= 4; i++)
    {
        int px = x + dx[i];
        int py = y + dy[i];
        if (px >= 1 && px <= r && py >= 1 && py <= c)//不越界
        {
            if (a[px][py] < a[x][y])//滑雪只能滑向高度小的坐标
            {
                //sum = max(ans,dfs(px, py, t + 1));//步数t每次加+1,每次取最大的给sum
                b[x][y] = max(b[x][y], 1 + dfs(px, py));//记录最大的步数
            }
        }
    }
    return b[x][y];
}
int main()
{
    cin >> r >> c;
    for (int i = 1; i <= r; i++)
    {
        for (int j = 1; j <= c; j++)
            cin >> a[i][j];
    }
    for (int i = 1; i <= r; i++)
    {
        for (int j = 1; j <= c; j++)
            //dfs(i, j, 0);//步数一上来从0开始
            dfs(i, j);
    }
    for (int i = 1; i <= r; i++)
    {
        for (int j = 1; j <= c; j++)
        {
            tns = max(tns, b[i][j]);//找最大步数
        }
    }
    cout << tns;
    return 0;
}

by Dreamerlee✅ @ 2021-04-06 21:23:11

@metaphysis 我就想知道为什么不能是return t + b[x][y]

by metaphysis @ 2021-04-06 23:40:13

@Dreamerlee✅

对样例数据稍加更改（将高度 18 改为 1）：

5 5
1 2 3 4 5
16 17 1 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

再在您的代码中增加调试语句，输出所有的 b[i][j]：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int r, c, a[110][110], b[110][110], sum, tns = -0x7777777,ans=-0x7777777;
int dx[5] = { 0,1,-1,0,0 };
int dy[5] = { 0,0,0,-1,1 };
int dfs(int x, int y, int t)//t代表步数
{
    if (b[x][y])
        return t + b[x][y];//步数加上之前记忆的数组的值
    b[x][y] = 1;//既然这是一个从未走过的点那么现在来到该点至少都会使其步数为1 
    for (int i = 1; i <= 4; i++)
    {
        int px = x + dx[i];
        int py = y + dy[i];
        if (px >= 1 && px <= r && py >= 1 && py <= c)//不越界
        {
            if (a[px][py] < a[x][y])//滑雪只能滑向高度小的坐标
            {
                sum = max(ans,dfs(px, py, t + 1));//步数t每次加+1,每次取最大的给sum
                b[x][y] = max(b[x][y], sum);//记录最大的步数
            }
        }
    }
    return b[x][y];
}
int main()
{
    cin >> r >> c;
    for (int i = 1; i <= r; i++)
    {
        for (int j = 1; j <= c; j++)
            cin >> a[i][j];
    }
    for (int i = 1; i <= r; i++)
    {
        for (int j = 1; j <= c; j++)
            dfs(i, j, 0);//步数一上来从0开始
    }
    for (int i = 1; i <= r; i++)
    {
        for (int j = 1; j <= c; j++)
        {
            cout << b[i][j] << ' ';
            tns = max(tns, b[i][j]);//找最大步数
        }
        cout << '\n';
    }
    cout << tns;
    return 0;
}

您的代码最终输出：

1 2 3 4 5 
16 17 1 17 16 
16 22 23 22 16 
16 22 22 22 16 
16 16 16 16 16 
23

即最长滑坡的长度为 23，但是正确的输出应该是：

1 2 3 4 5 
16 17 1 7 6 
15 18 19 8 7 
14 15 12 11 8 
13 12 11 10 9 
19

即最长的滑坡长度为 19。

您自己一步一步调试看，为什么不能返回 t + b[x][y]。

by Dreamerlee✅ @ 2021-04-07 09:35:06

@metaphysis 谢谢大佬