90分求助

SCP3023 @ 2024-07-29 15:15:13

#include<bits/stdc++.h>//记忆化搜索
using namespace std;
int r,c,mp[1001][1001];
int sum[1001][1001];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
void Dfs(int x,int y){
    int flag=0;
    for(int i=0;i<4;i++){
        if(mp[x+dx[i]][y+dy[i]]<mp[x][y]){
            flag=1;
            if(sum[x+dx[i]][y+dy[i]]==0){
                Dfs(x+dx[i],y+dy[i]);
            }
            sum[x][y]=max(sum[x][y],sum[x+dx[i]][y+dy[i]]+1);
        }
    }
    if(flag==0){
        sum[x][y]=1;
    }
    return;
}
int main(){
    cin>>r>>c;
    for(int i=0;i<=r;i++){//边界框
        mp[i][0]=10000001;
        mp[0][i]=10000001;
        mp[i][r+1]=10000001;
        mp[r+1][i]=10000001;
    }
    mp[r+1][r+1]=10000001;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>mp[i][j];
        }
    } 
    int mx=1;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            if(sum[i][j]==0){
                Dfs(i,j);
            }
            if(sum[i][j]>=mx){
                mx=sum[i][j];   
            }
        }
    }
    cout<<mx;
    return 0;
}

by SCP3023 @ 2024-07-29 15:16:10

wa了一个点

by wsgdsgqq @ 2024-08-04 10:18:52

@SCP3023 你的边界框设置得有问题， r有可能不等于c

by wsgdsgqq @ 2024-08-04 10:19:21

@SCP3023 可以试试这样打

#include<bits/stdc++.h>//记忆化搜索
using namespace std;
int r,c,mp[1010][1010];
int sum[1010][1010];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
void Dfs(int x,int y){
    int flag=0;
    for(int i=0;i<4;i++)
    {
        if(mp[x+dx[i]][y+dy[i]]<mp[x][y])
        {
            if(x+dx[i]<1||x+dx[i]>r||y+dy[i]<1||y+dy[i]>c)
                continue;
            flag=1;

            if(sum[x+dx[i]][y+dy[i]]==0)
                Dfs(x+dx[i],y+dy[i]);
            sum[x][y]=max(sum[x][y],sum[x+dx[i]][y+dy[i]]+1);
        }
    }
    if(flag==0){
        sum[x][y]=1;
    }
    return;
}
int main(){
    cin>>r>>c;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>mp[i][j];
        }
    } 
    int mx=1;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            if(sum[i][j]==0){
                Dfs(i,j);
            }
            if(sum[i][j]>=mx){
                mx=sum[i][j];   
            }
        }
    }
    cout<<mx;
    return 0;
}

by SCP3023 @ 2024-08-04 11:20:34

哦哦哦，感谢感谢

by SCP3023 @ 2024-08-04 11:21:48

此棺结