#1Wa求助

P1434 [SHOI2002] 滑雪

Fr0sTy @ 2022-03-24 20:47:41

RT.

#include<bits/stdc++.h>
using namespace std;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int n,m,maps[1005][1005],bx,by,maxx=-1,minn=0x3f3f3f3f,ans=0,maxn=-1;
int memery[1005][1005];
void dfs(int x,int y,int sum) {
    if(maps[x][y]==minn) {
        maxn=max(maxn,sum);
        return;
    }
    else if(memery[x][y]!=0) {
        maxn=max(maxn,sum+memery[x][y]-1);
        return;
    }
    else {
        for(int i=0;i<4;i++) {
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(xx>0&&xx<=n&&yy>0&&yy<=m&&maps[xx][yy]<maps[x][y]) {
                dfs(xx,yy,sum+1);
            }
        }
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            scanf("%d",&maps[i][j]);
            if(maps[i][j]<minn) {
                minn=maps[i][j];
            }
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            maxn=0;
            dfs(i,j,1);
            ans=max(ans,maxn);
            memery[i][j]=maxn;
        }
    }
    cout<<ans;
    return 0;
}

|