【违规紫衫】有大佬吗？

Leo2020 @ 2021-07-24 22:40:30

#include<bits/stdc++.h>
using namespace std;
const int XY[5]={1,0,-1,0,1};
int n,m,num[1015][1015],ans;
void dfs(int x,int y,int s,int t){
    for(int i=0;i<5;i++){
        int X=x+XY[i],Y=y+XY[i+1];
        if(0<=X<n&&0<=Y<m&&num[X][Y]<s){
            dfs(X,Y,num[X][Y],t+1);
        }
    }
    ans=max(ans,t);
}
int main(){
    cin >> n >> m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> num[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            dfs(i,j,num[i][j],0);
        }
    }
    cout << ans << endl;
    return 0;
}

by Leo2020 @ 2021-07-24 22:41:21

题目传送门

by SSL_wj @ 2021-07-24 22:46:25

＜5？？？

by Loser_King @ 2021-07-24 22:46:32

if(0<=X<n&&0<=Y<m&&num[X][Y]<s){

c++ 里并不能连续使用<和<=

拆开即可

by Loser_King @ 2021-07-24 22:48:04

还有，因为方向只有4个，所以方向数组应该只开i=0;i<4;i++

by Loser_King @ 2021-07-24 22:48:59

我也不是大佬（捂脸）

by Leo2020 @ 2021-07-24 22:49:04

@Loser_King 谢谢

by Leo2020 @ 2021-07-24 22:49:23

@SSL_wj 啊！大意了！

by Leo2020 @ 2021-07-24 22:50:34

@Loser_King ac这么多题，还不大佬？

by Leo2020 @ 2021-07-24 22:55:45

现在又第二个点超时了，其他点都ac了，还有大佬吗QAQ

#include<bits/stdc++.h>
using namespace std;
const int XY[5]={1,0,-1,0,1};
int n,m,num[1015][1015],ans;
void dfs(int x,int y,int s,int t){
    for(int i=0;i<4;i++){
        int X=x+XY[i],Y=y+XY[i+1];
        if(0<=X&&X<n&&0<=Y&&Y<m&&num[X][Y]<s){
            dfs(X,Y,num[X][Y],t+1);
        }
    }
    ans=max(ans,t);
}
int main(){
    cin >> n >> m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> num[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            dfs(i,j,num[i][j],1);
        }
    }
    cout << ans << endl;
    return 0;
}

by BlankAo @ 2021-07-24 23:13:06

@Leo2020 这道题需要记忆化dfs，你可以看看题解。简要来说，如果你知道一个点的最优解，下一次来到这个点就可以直接用此最优解更新，而不是继续寻找。