60分求调,思路如下

P1434 [SHOI2002] 滑雪

Ice_Fist @ 2024-02-20 09:34:53

先从最低位开始,不断枚举最接近的高位, 直到无法继续为止。 代码如下:

#include<bits/stdc++.h> 
using namespace std ;
int r,c,minn=0x7f,mini,minj,maxn=0xff,maxi,maxj;
int mmn=0x7f,mmni,mmnj,ans=0;
int a[101][101]={-1};
int i=1,j=1;
int _=1;
signed main(){  
    cin>>r>>c;
    for(i=1;i<=r;++i){
        for(j=1;j<=c;++j){
            cin>>a[i][j];
            if(a[i][j]<minn){
                minn=a[i][j];
                mini=i;
                minj=j;
            }
            if(a[i][j]>maxn){
                maxn=a[i][j];
                maxi=i;
                maxj=j;
            }
        }
    }
    i=mini,j=minj;
    int v=0,b=0,n=0,m=0;
    while(_++){
        v=0,b=0,n=0,m=0;
        mmn=0x7f;
        if(a[i+1][j]>a[i][j]&&a[i+1][j]<mmn){
            mmn=a[i+1][j];
            mmni=i+1;
            mmnj=j;
            v=1;
        }
        if(a[i][j+1]>a[i][j]&&a[i][j+1]<mmn){
            mmn=a[i][j+1];
            mmni=i;
            mmnj=j+1;
            b=1;
        }
        if(a[i-1][j]>a[i][j]&&a[i-1][j]<mmn){
            mmn=a[i-1][j];
            mmni=i-1;
            mmnj=j;
            m=1;
        }
        if(a[i][j-1]>a[i][j]&&a[i][j-1]<mmn){
            mmn=a[i][j-1];
            mmni=i;
            mmnj=j-1;
            n=1;
        }
        i=mmni;
        j=mmnj;
        ans++;
        if(v==0&&b==0&&n==0&&m==0){
            break;
        } 
    }
    cout<<ans;
}

|