20pts，有WA有RE，DFS求调

yangcenyou @ 2024-07-10 16:16:44

#include <bits/stdc++.h>
using namespace std;
int ans=-114514,cnt=1;
int a[13][13],col[13][13];
void dfs(int n,int m){
    col[n][m]=1;
    if(a[n+1][m]!=-1&&a[n+1][m]<a[n][m]&&!col[n+1][m]){
        cnt++;
        dfs(n+1,m);
    }
    if(a[n-1][m]!=-1&&a[n-1][m]<a[n][m]&&!col[n-1][m]){
        cnt++;
        dfs(n-1,m);
    }
    if(a[n][m+1]!=-1&&a[n][m+1]<a[n][m]&&!col[n+1][m]){
        cnt++;
        dfs(n,m+1);
    }
    if(a[n][m-1]!=-1&&a[n][m-1]<a[n][m]&&!col[n+1][m]){
        cnt++;
        dfs(n,m-1);
    }
    return ;
}
int main(){
    int r,c;
    memset(a,-1,sizeof(a));
    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++){
            memset(col,0,sizeof(col));
            cnt=0;
            dfs(i,j);
            ans=max(ans,cnt);
        }
    }
    cout<<ans;
}

by tankewei911 @ 2024-07-10 16:22:28

//状态(x,y, sum)现在在滑雪场第x行，第y列滑坡的总和为sum;
//转移(x,y, sum) -> (x + dx[i], y + dy[i], sum + 1) 还要a[x + dx[i]][y + dy[i]] < a[x][y];
//初始状态 从滑雪场i,j开始 1 <= i <= n && 1 <= j <= m；
//目标状态 当到了没有上坡了 滑坡的总次数越大越好；
#include<bits/stdc++.h>

using namespace std;

const int MAXX = 105;
const int dx[] = {1, 0 ,-1, 0};
const int dy[] = {0, -1, 0, 1};

int n, m, a[MAXX][MAXX], dp[MAXX][MAXX], ans;

void S(int x, int y, int sum){
  if(x < 1 || y < 1 || x > n || y > m || sum <= dp[x][y]){
    return;
  }
  ans = max(ans, sum);
  dp[x][y] = sum;
  for(int i = 0; i < 4; i++){
    if(a[x + dx[i]][y + dy[i]] < a[x][y]){
      S(x + dx[i], y + dy[i], sum + 1);
    }
  }
}

int main(){
  cin >> n >> m;
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      cin >> a[i][j];
      dp[i][j] = -1;
    }
  }
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      S(i, j, 1);
    }
  }
  cout << ans;
  return 0;
}

by tankewei911 @ 2024-07-10 16:24:05

@yangcenyou 首先R和C都小于等于100，你数组开小了

by a18981826590 @ 2024-07-10 16:34:07

@yangcenyou

#include<bits/stdc++.h>
using namespace std;
int a[110][110],e[110][110],m,n,s;
int b(int c,int d){
    if(e[c][d]) return e[c][d];
    if(a[c-1][d]<a[c][d]&&c>1) e[c][d]=max(b(c-1,d),e[c][d]);
    if(a[c+1][d]<a[c][d]&&c<m) e[c][d]=max(b(c+1,d),e[c][d]);
    if(a[c][d-1]<a[c][d]&&d>1) e[c][d]=max(b(c,d-1),e[c][d]);
    if(a[c][d+1]<a[c][d]&&d<n) e[c][d]=max(b(c,d+1),e[c][d]);
    return ++e[c][d];
}
int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++) scanf("%d",&a[i][j]);
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++) s=max(b(i,j),s);
    }
    printf("%d",s);
    return 0;
}

by tankewei911 @ 2024-07-10 16:38:25

@yangcenyou 其次我建议你判断越界用 1<=x+1<=n这种还有你的cnt不是一条道路的长度而是dfs里所有遍历过的道路长度总和

by tankewei911 @ 2024-07-10 16:39:49

#include <bits/stdc++.h>
using namespace std;
int ans=-114514,cnt=1;
int r,c;
int a[1000][1000],col[1000][1000];
void dfs(int n,int m,int sum){
    //cout << cnt << " " << n << " " << m << " " << sum << '\n';
    cnt=max(cnt,sum);
    if(n+1<=r&&a[n+1][m]<a[n][m]){
        dfs(n+1,m,sum+1);
    }
    if(n-1>=1&&a[n-1][m]<a[n][m]){
        dfs(n-1,m,sum+1);
    }
    if(m+1<=c&&a[n][m+1]<a[n][m]){
        dfs(n,m+1,sum+1);
    }
    if(m-1>=1&&a[n][m-1]<a[n][m]){
        dfs(n,m-1,sum+1);
    }
    return ;
}
int main(){
    memset(a,-1,sizeof(a));
    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++){
            memset(col,0,sizeof(col));
            cnt=0;
            dfs(i,j,1);
            //cout << cnt << '\n';
            ans=max(ans,cnt);
        }
    }
    cout<<ans;
}

@yangcenyou 这是改后的但时间复杂度会超时

by tankewei911 @ 2024-07-10 16:43:10

@yangcenyou 所以我们要用一个记忆数组来记从这个点开始的最长路径如果遍历到的这个点知道从这个点开始的最长路径就可以直接用，便不会超时了

by tankewei911 @ 2024-07-10 16:46:15

@yangcenyou AC代码

#include <bits/stdc++.h>
using namespace std;
int ans=-114514,cnt=1;
int r,c;
int a[1000][1000],num[1000][1000];
void dfs(int n,int m,int sum){
    //cout << cnt << " " << n << " " << m << " " << sum << '\n';
    if(num[n][m]!=0){
        cnt=max(cnt,sum+num[n][m]-1);
        return;
    }
    cnt=max(cnt,sum);
    if(n+1<=r&&a[n+1][m]<a[n][m]){
        dfs(n+1,m,sum+1);
    }
    if(n-1>=1&&a[n-1][m]<a[n][m]){
        dfs(n-1,m,sum+1);
    }
    if(m+1<=c&&a[n][m+1]<a[n][m]){
        dfs(n,m+1,sum+1);
    }
    if(m-1>=1&&a[n][m-1]<a[n][m]){
        dfs(n,m-1,sum+1);
    }
    return ;
}
int main(){
    memset(a,-1,sizeof(a));
    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++){
            cnt=0;
            dfs(i,j,1);
            //cout << cnt << '\n';
            num[i][j] = cnt;
            ans=max(ans,cnt);
        }
    }
    cout<<ans;
}