广搜为啥80分,哪里有错?

P1434 [SHOI2002] 滑雪

jping @ 2022-12-28 15:22:19

#include<iostream>
#include<queue>
using namespace std;
struct T{
    int x,y;
}sT,now;
queue<T>AA;
int a[103][103],dp[103][103];
int main(){
    int r,c,ans=1,flag;
    cin>>r>>c;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)cin>>a[i][j];
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++){
            if(a[i][j]>=a[i-1][j] && a[i][j]>=a[i][j-1] && a[i][j]>=a[i][j+1] && a[i][j]>=a[i+1][j]){
                sT.x=i;
                sT.y=j;
                dp[i][j]=1;
                AA.push(sT);
            }
        }
    while(!AA.empty()){
        now=AA.front();
        AA.pop();
//      cout<<now.x<<" "<<now.y<<" "<<dp[now.x][now.y]<<endl;
        if(now.x>1 && dp[now.x-1][now.y]==0){
            flag=0;
            if(dp[now.x-2][now.y]==0 && a[now.x-1][now.y]<a[now.x-2][now.y])flag++;
            if(dp[now.x-1][now.y-1]==0 && a[now.x-1][now.y]<a[now.x-1][now.y-1])flag++;
            if(dp[now.x-1][now.y+1]==0 && a[now.x-1][now.y]<a[now.x-1][now.y+1])flag++;
            if(flag==0){
                sT.x=now.x-1;
                sT.y=now.y;
                dp[now.x-1][now.y]=dp[now.x][now.y]+1;
                AA.push(sT);
            }
        } 
        if(now.y>1 && dp[now.x][now.y-1]==0){
            flag=0;
            if(dp[now.x-1][now.y-1]==0 && a[now.x][now.y-1]<a[now.x-1][now.y-1])flag++;
            if(dp[now.x][now.y-2]==0 && a[now.x][now.y-1]<a[now.x][now.y-2])flag++;
            if(dp[now.x+1][now.y-1]==0 && a[now.x][now.y-1]<a[now.x+1][now.y-1])flag++;
            if(flag==0){
                sT.x=now.x;
                sT.y=now.y-1;
                dp[now.x][now.y-1]=dp[now.x][now.y]+1;
                AA.push(sT);
            }
        } 
        if(now.y<c && dp[now.x][now.y+1]==0){
            flag=0;
            if(dp[now.x-1][now.y+1]==0 && a[now.x][now.y+1]<a[now.x-1][now.y+1])flag++;
            if(dp[now.x][now.y+2]==0 && a[now.x][now.y+1]<a[now.x][now.y+2])flag++;
            if(dp[now.x+1][now.y+1]==0 && a[now.x][now.y+1]<a[now.x+1][now.y+1])flag++;
            if(flag==0){
                sT.x=now.x;
                sT.y=now.y+1;
                dp[now.x][now.y+1]=dp[now.x][now.y]+1;
                AA.push(sT);
            }
        } 
        if(now.x<r && dp[now.x+1][now.y]==0){
            flag=0;
            if(dp[now.x+2][now.y]==0 && a[now.x+1][now.y]<a[now.x+2][now.y])flag++;
            if(dp[now.x+1][now.y-1]==0 && a[now.x+1][now.y]<a[now.x+1][now.y-1])flag++;
            if(dp[now.x+1][now.y+1]==0 && a[now.x+1][now.y]<a[now.x+1][now.y+1])flag++;
            if(flag==0){
                sT.x=now.x+1;
                sT.y=now.y;
                dp[now.x+1][now.y]=dp[now.x][now.y]+1;
                AA.push(sT);
            }
        } 
    }
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++){
            ans=max(ans,dp[i][j]);
        }
    cout<<ans;
    return 0;
}

|