WA#1,8,9,10 MLE#2 50tps求调

P1434 [SHOI2002] 滑雪

yinzixia @ 2024-11-17 16:22:39

#include<bits/stdc++.h>
using namespace std;
int a[105][105],r,c;
struct yyy{
    int id,l,x,y;
};
queue<yyy> q;
int dx[4]={1,0,0,-1},dy[4]={0,1,-1,0};
int main(){
    cin>>r>>c;
    int x1,y1;
    int max_=-99999999;
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            cin>>a[i][j];
            max_=max(max_,a[i][j]);
            if(a[i][j]==max_){
                x1=i;
                y1=j;
            }
        }
    }
    int ans=-9999;
    q.push((yyy){max_,1,x1,y1});
    while(q.empty()==false){
        ans=max(ans,q.front().l);
        int x=q.front().x,y=q.front().y;
        for(int i=0;i<4;i++){
            int xx=x+dx[i],yy=y+dy[i];
            if(xx>=0&&xx<r&&yy>=0&&yy<c){
                if(a[x][y]>a[xx][yy]){
                    q.push((yyy){a[xx][yy],q.front().l+1,xx,yy});
                }
            }
        }
        q.pop();
    }
    cout<<ans;
    return 0;
} 

by Lazy_Durant @ 2024-11-19 21:35:32

@yinzixia


by Lazy_Durant @ 2024-11-19 21:38:36

你应该是想从最大的点开始走,使用BFS探究最大长度,但是有一个bug 比如

100 0 3 2 1

0 0 2 2 1

这组数据用你的代码,只有100会入队,但是显然最长的长度不是从100开始走,答案应该是DFS+记忆化


by yinzixia @ 2024-11-21 20:15:57

@Lazy_Durant 谢谢大佬


|