蒟蒻求助!!!

P1434 [SHOI2002] 滑雪

yokuma @ 2019-01-02 19:28:42

#include<bits/stdc++.h>
using namespace std;
const int N=-1e9; 
int max(int a,int b){return a>b?a:b;}
int bian1[5]={0,1,-1,0,0},bian2[5]={0,0,0,1,-1};
struct xue{
    int x,y,gao,cnt;
    xue(int a=0,int b=0,int c=0):x(a),y(b),gao(c),cnt(0){}
    bool operator<(xue a)const{return gao<a.gao;}
};
int tu[115][115]={0};
priority_queue <xue> you;
int bfs(int x1,int y1){
    int head(0),tail(1),zuida(0);
//  memset(dp,0,sizeof(dp));
    xue dp[10050];
    bool isv[104][104]={0};
    dp[head]=xue(x1,y1,tu[x1][y1]);
    dp[head].cnt=1;
    while(tail>head){
        int xx=dp[head].x,yy=dp[head].y,h=dp[head].gao,ji=dp[head].cnt;
        for(int i(1);i<=4;i++){
            if(isv[xx+bian1[i]][yy+bian2[i]]==0&&tu[xx+bian1[i]][yy+bian2[i]]!=N&&h>tu[xx+bian1[i]][yy+bian2[i]]){
                isv[xx+bian1[i]][yy+bian2[i]]=1;
                dp[tail].x=xx+bian1[i];
                dp[tail].y=yy+bian2[i];
                dp[tail].gao=tu[xx+bian1[i]][yy+bian2[i]];
                dp[tail].cnt=ji+1;
                zuida=max(zuida,dp[tail].cnt);
                tail++;
            }
            isv[xx+bian1[i]][yy+bian2[i]]=0;
        }
        head++;
    }
    return zuida;
}
int main(){
    int hang,lie,high(0),zuizhi(0);
    scanf("%d%d",&hang,&lie);
    for(int i(0);i<=114;i++){
        for(int j(0);j<=114;j++){
        tu[i][j]=N;
        }
    }
    for(int i(1);i<=hang;i++){
        for(int j(1);j<=lie;j++){
            scanf("%d",&high);
            xue zj=xue(i,j,high);
            you.push(zj);
            tu[i][j]=high;
        }
    }
    if(hang==lie&&hang==1){
        printf("1");
        return 0;
    }
    while(!you.empty()){
        int xx1=you.top().x,yy1=you.top().y,g=you.top().gao;
        you.pop();
        if(zuizhi>g){break;}
        zuizhi=max(zuizhi,bfs(xx1,yy1));
    }
    printf("%d",zuizhi);
}
  • 写的广搜好像有点奇怪,到底有没有回溯的那一步啊,虽然得了80分但剩下的两个点实在不知道这么做,求各位大佬指点。

by ENDKING @ 2019-01-02 19:29:22

你太强了%%%

|