0pts 求助orz

Calarence4 @ 2023-10-16 21:12:19

#include<bits/stdc++.h>
using namespace std;

int R,C;
int h[105][105];
int mem[105][105];
int dx[4]={0,0,-1,+1},dy[4]={-1,+1,0,0};//上下左右
int dfs(int,int);
int main(){
    cin>>R>>C;
    for(int i=1;i<=R;i++){
        for(int j=1;j<=C;j++){
            cin>>h[i][j];
        }
    }
    memset(mem,-1,sizeof(mem));
    int Max=0;
    for(int i=1;i<=R;i++){
        for(int j=1;j<=C;j++){
            Max=max(Max,dfs(i,j));
        }
    }
    cout<<Max;
}
int dfs(int r,int c){
    if(mem[r][c]!=-1){
        return mem[r][c];
    }
    if(h[r][c]<=0){
        return 0;
    }
    for(int i=0;i<4;i++){
        if(h[r+dx[i]][c+dy[i]]<h[r][c]){
            mem[r][c]=dfs(r+dx[i],c+dy[i]);
            return  mem[r][c];
        }
    }
    mem[r][c]=0;
    return 0;
}

by Carl170679 @ 2023-10-16 21:22:31

#include <iostream>
using namespace std;

const int MAX_N = 250; // 最大行数
const int MAX_M = 250; // 最大列数
int n, m, matrix[MAX_N][MAX_M], ans[MAX_N][MAX_M]; // 原始矩阵和结果矩阵
int dx[5] = {0, 0, 0, -1, 1}; // x方向的增量（上下左右）
int dy[5] = {0, 1, -1, 0, 0}; // y方向的增量（上下左右）

int dfs(int x, int y) {
    if (ans[x][y])
        return ans[x][y]; // 如果结果矩阵已经计算过，则直接返回结果
    if (x < 1 || x > n || y < 1 || y > m)
        return 0; // 越界情况下，路径长度为0
    bool flag = false;
    for (int i = 1; i <= 4; i++) {
        int x1 = x + dx[i];
        int y1 = y + dy[i];
        if (matrix[x1][y1] < matrix[x][y]) {
            ans[x][y] = max(ans[x][y], 1 + dfs(x1, y1)); // 递归计算最长路径，取最大值
            flag = true;
        }
    }
    if (!flag) {
        ans[x][y] = 1; // 如果无法继续走，则路径长度为1
        return 1;
    }
    return ans[x][y]; // 返回结果矩阵中的路径长度
}

int main() {
    cin >> n >> m; // 输入矩阵的行数和列数
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> matrix[i][j]; // 输入矩阵元素的值
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (!ans[i][j])
                dfs(i, j); // 对每个位置进行深度优先搜索
        }
    int maxans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            maxans = max(maxans, ans[i][j]); // 找到结果矩阵中的最大路径长度
    cout << maxans << endl; // 输出最大路径长度
    return 0;
}

对照一下，自己改改

by Carl170679 @ 2023-10-16 21:23:41

@Calarence4 不要脸的求个关注

by Calarence4 @ 2023-10-17 18:53:02

@Carl0626 thx,已关注

by Calarence4 @ 2023-10-17 23:09:09

@Carl0626 flag指的作用是为了判断不能走的情况吗？直接在循环之后return ans是不是也可以。

by Calarence4 @ 2023-10-17 23:28:28

@Carl0626 为什么没路走的时候返回值为1

by Calarence4 @ 2023-10-17 23:38:13

我发现我的代码在无路可走时，返回值为1和0分别能对一半的点 还是不知道哪错了，求指点orz

#include<bits/stdc++.h>
using namespace std;

int R,C;
int h[105][105];
int mem[105][105];
int dx[4]={0,0,-1,+1},dy[4]={-1,+1,0,0};//上下左右
int dfs(int,int);
int main(){
    cin>>R>>C;//输入行,列
    for(int i=1;i<=R;i++){
        for(int j=1;j<=C;j++){
            cin>>h[i][j];
        }
    }
    memset(mem,-1,sizeof(mem));//初始化记忆数组,-1表示未访问
    int ans=0;
    for(int i=1;i<=R;i++){
        for(int j=1;j<=C;j++){
            ans=max(ans,dfs(i,j));//答案为全部点下滑的最大高度的最大值
        }
    }
    cout<<ans<<"\n";
}

int dfs(int r,int c){
    if(mem[r][c]!=-1){//已经搜索过直接返回
        return mem[r][c];
    }
    if(r<1||r>R||c<1||c>C){//越界
        mem[r][c] = 0;
    }
    bool flag=false;//起始标记为无路可走
    for(int i=0;i<4;i++){//分别搜索四个方位比较最大高度
        if(h[r+dx[i]][c+dy[i]]<h[r][c]){
            flag=true;//有路可走
            mem[r][c]=max(mem[r][c],dfs(r+dx[i],c+dy[i])+1);//+1算上当前点
        }
    }
    if(flag==false){
        mem[r][c]=0;//无路可走
    }
    return mem[r][c];
}