全部WA了

P1434 [SHOI2002] 滑雪

Chtholly_is_cute @ 2023-10-03 16:13:02

code:

#include<iostream>
#include<algorithm>
using namespace std;
int a[105][105];
int f[105][105];
int n, m;
int dx[4] = { 0,1,-1,0 };
int dy[4] = { -1,0,0,1 };
int dfs(int x, int y) {
    cout << x << ' ' << y << endl;
    if (f[x][y])return f[x][y];
    f[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int xx = dx[i] + x;
        int yy = dx[i] + y;
        if (xx > 0 && xx < n && yy>0 && yy<m && a[x][y]>a[xx][yy]) {
            f[xx][yy] = dfs(xx, yy);
            f[x][y] = max(f[x][y], f[xx][yy] + 1);
        }
    }
    return f[x][y];
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    int ans = -1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ans = max(ans, dfs(i, j));
        }
    }
    cout << ans << endl;
    return 0;
}

by TemplateClass @ 2023-10-03 16:16:04

能大致解释一下思路吗……

没看懂 qwq。


by TemplateClass @ 2023-10-03 16:16:29

@andyzhu444


by fangyicheng1216 @ 2023-10-03 16:21:44

还要加一个 vis 数组来判重。


by Max6700 @ 2023-10-03 16:23:33

@fangyicheng1216 正解


by _FastFT2013 @ 2023-10-14 14:19:49

错误:

记忆化搜索那里xx>0&&xx<n&&yy>0&&yy<m
改成xx>0&&xx<=n&&yy>0&&yy<=m

by _FastFT2013 @ 2023-10-14 14:22:04

@andyzhu444


by Chtholly_is_cute @ 2023-10-14 14:32:26

@wuxiuyuan thnks


|