TLE#2,求调

P1434 [SHOI2002] 滑雪

wanghaolin2013 @ 2024-08-22 08:09:10

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

int m, n, a[202][202], s = INT_MIN;

int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0}, c = 0;

void dfs(int x, int y, int l) {
    s = max(l, s);
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] < a[x][y]) {
            dfs(nx, ny, l + 1);
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dfs(i, j, 1);
        }
    }
    printf("%d", s);
    return 0;
}

by szrgjxms @ 2024-08-22 08:25:50

要不试一试记忆化搜索?!


by szrgjxms @ 2024-08-22 08:29:06

用带返回值 (int) 的 dfs 会好写很多,多开一个数组来记录就可以了。


by wanghaolin2013 @ 2024-08-22 08:41:53

能多给点提示吗?


by szrgjxms @ 2024-08-22 09:10:18

在你进去搜索的时候,你可以先判断一下,如果当前这个点(x,y)是已经“走过”的,你就返回它的值(记录的时候记录最大值)。


by szrgjxms @ 2024-08-22 09:10:53

抱歉,刚才在听课,没看见


by szrgjxms @ 2024-08-22 09:42:56

@wanghaolin2013 做出来了不?要是真的做不出来,就去学一学,点这里


|