90pts,有优化空间否?

P1434 [SHOI2002] 滑雪

KK_lang @ 2022-11-08 18:39:49

思路:DFS,#2 T掉了,求如何优化。

#include<bits/stdc++.h>
using namespace std;

int n, m, ans;
int a[110][110];
bool vis[110][110];

void dfs(int x, int y, int step)
{
    if (x < 1 || x > n || y < 1 || y > m) return;
    if (vis[x][y]) return;
    vis[x][y] = true;
    ans = max(ans, step);
    if (a[x][y] > a[x + 1][y]) dfs(x + 1, y, step + 1);
    if (a[x][y] > a[x][y + 1]) dfs(x, y + 1, step + 1);
    if (a[x][y] > a[x - 1][y]) dfs(x - 1, y, step + 1);
    if (a[x][y] > a[x][y - 1]) dfs(x, y - 1, step + 1);
    vis[x][y] = false;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dfs(i, j, 1);
    cout << ans << endl;
    return 0;
}

感谢各位大佬


by xiaoPanda @ 2022-11-08 18:43:43

@KK_lang 记忆化搜索。


by KK_lang @ 2022-11-08 18:46:31

@xiaoPanda 艹谢谢,但是我已经几乎彻底忘记记忆化了。。。


by Tu_es_trop_belle @ 2022-11-08 19:35:15

@KK_lang 提示:第二个点答案是9900


by KK_lang @ 2022-11-08 22:49:56

@Tu_es_trop_belle 。。。


|