dfs+记忆化搜索 tle第二个点

向晚 @ 2021-05-26 19:24:34

#include<iostream>
using namespace std;
int n,m,map[105][105],f[105][105],ans;

int m1[4]={-1,0,0,1};
int m2[4]={0,-1,1,0};
void dfs(int x,int y,int s){
    if(f[x][y]>=s) return ;
    f[x][y]=s;
    for(int i=0;i<4;i++){
        int mx=x+m1[i],my=y+m2[i];
        if(map[mx][my]>=map[x][y]) continue;
        if(mx<1||mx>n||my<1||my>m) continue;
        dfs(mx,my,s+1);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>map[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(!f[i][j]) dfs(i,j,1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            ans=max(ans,f[i][j]);
    cout<<ans;
    return 0;
}

by JRzyh @ 2021-05-26 19:28:25

@向晚 卡常

by 向晚 @ 2021-05-26 19:32:59

@Zhaoyuhang2008 怎么卡呐

by 小王同学哦 @ 2021-05-26 19:33:50

#include<iostream>
using namespace std;
int n,m,map[105][105],f[105][105],ans;
int m1[4]= {-1,0,0,1};
int m2[4]= {0,-1,1,0};
inline int read() {//数据较大用快读 
    int f=1,x=0;
    char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
void dfs(int x,int y,int s) {
    if(f[x][y]>=s) return ;
    f[x][y]=s;
    for(int i=0; i<4; i++) {
        int mx=x+m1[i],my=y+m2[i];
        if(map[mx][my]>=map[x][y]) continue;
        if(mx<1||mx>n||my<1||my>m) continue;
        dfs(mx,my,s+1);
    }
}
int main() {
    n=read(),m=read();
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            map[i][j]=read();
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(!f[i][j]) dfs(i,j,1);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            ans=max(ans,f[i][j]);
    printf("%d",ans);
    return 0;
}

by JRzyh @ 2021-05-26 19:34:19

@向晚 就0.02s随便卡卡就过了吧

cin->scanf

加register

by 小王同学哦 @ 2021-05-26 19:34:40

实测920ms

by 向晚 @ 2021-05-26 19:35:01

谢谢大佬！

by 小王同学哦 @ 2021-05-26 19:36:39

@向晚 感谢巨佬的code，又A了一题/xyx

by W_SUN @ 2021-05-26 19:48:29

@向晚 开o2

by Aukari @ 2021-05-26 20:18:01

c我用的是py卑微