50分,实在是改不出来,都五次了。。。求dalao相助100分。。

P1434 [SHOI2002] 滑雪

Surpersolo @ 2019-08-20 09:27:40

#include<bits/stdc++.h>
using namespace std;
int a[110][110],f[110][110];
const int dx[]= {1,0,-1,0};
const int dy[]= {0,1,0,-1};
struct edge {
    int x,y,u;
} e[4];
bool dp(edge a,edge b) {
    return a.u<b.u;
}
void dfs(int z,int x,int y) {
    if (f[x][y]>=z)return ;
    f[x][y]=z;
    for(int i=0; i<4; i++) {
    e[i].x=x+dx[i];
        e[i].y=y+dy[i];
        e[i].u=a[e[i].x][e[i].y];
    }
    sort(e,e+4,dp);
    for(int i=0; i<4; i++) {
        if (e[i].u!=-1&&e[i].u>=z) {
            dfs(z+1,e[i].x,e[i].y);
        }
    }
    return ;
}
int main() {
    int n,m;
    cin>>n>>m;
    memset(a,-1,sizeof(a));
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin>>a[i][j];
        }
    }
    memset(f,-1,sizeof(f));
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if (f[i][j]==-1) {
                dfs(1,i,j);
            }
        }
    }
    int ans=0;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            ans=max(ans,f[i][j]);
        }
    }
    cout<<ans<<endl;
    return 0;
}

by Surpersolo @ 2019-08-20 09:28:21

我这题用的是深搜

by leoliao @ 2019-08-20 09:33:06

我用dfs


by Surpersolo @ 2019-08-20 09:37:03

好了 我对了 我后面用记忆化搜索ok了

|