3 solutions

  • 0
    @ 2024-10-27 20:41:12 
    n,m = map(int,input().split())
g = [list(map(int,input().split())) for _ in range(n)]
f = [[-1]*m for _ in range(n)]
dx = [1,-1,0,0]
dy = [0,0,-1,1]

def dfs(x,y):
    if f[x][y]!=-1:
        return f[x][y]
    f[x][y]=1
    t = 0
    for i in range(4):
        new_x = x + dx[i]
        new_y = y + dy[i]
        if 0<=new_x<n and 0<=new_y<m and g[new_x][new_y]<g[x][y]:
            t = max(t,dfs(new_x,new_y))
    f[x][y]+=t
    return f[x][y]

res = 0
for i in range(n):
    for j in range(m):
        res = max(res,dfs(i,j))
print(res)
    • 0
      @ 2024-9-27 9:46:40

      超时一个案例的bfs。。。

      #include <algorithm>
#include <bits/stdc++.h>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
vector<vector<int>> g;
vector<vector<int>> dp;
int r,c;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
int  dfs(int i,int j){
    queue<pair<int, int>> q;
    q.push({i,j});
    int cur=1;
    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        for (int i=0; i<4; i++) {
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx<0||ny<0||nx>=r||ny>=c){
                continue;
            }
            if (g[nx][ny]<g[x][y]) {
                dp[nx][ny]=max(dp[x][y]+1,dp[nx][ny]);
                cur=max(dp[nx][ny],cur);
                q.push({nx,ny});
            }
        }
    }
    return cur ;
   
}
int main(){
    
    cin>>r>>c;
    g.resize(r,vector<int>(c));
    dp.resize(r,vector<int>(c,1));
    for (int i=0; i<r; i++) {
        for (int j=0; j<c; j++) {
            cin>>g[i][j];
        }
    }
    int res=0;
    for (int i=0; i<r; i++) {
        for (int j=0; j<c; j++) {
           res=max(res,dfs(i,j));
        }
    }
    cout<<res<<endl;

}
      • 0
        @ 2024-8-21 4:19:17

        题面描述

        塔子哥是一位极限滑雪爱好者，他希望探索滑雪场的最长路径。给定一个滑雪场的高度矩阵，要求滑雪路径从一个点滑向周围的相邻点，且下一个点的高度必须严格低于当前点。输入包括矩阵的行数和列数，以及每个点的高度。输出最长的滑雪路径长度。你是否想要了解具体的解题思路或方法？

        题解：记忆化搜索

        定义f[i][j]f[i][j]表示以(i,j)(i,j)点开始的最大路径，由于只能向比它权值低的点走，因此对于所有可以前往的路径(a,b)(a,b)

        应该有f[i][j]=max(f[i][j],f[a][b]+1)f[i][j]=max(f[i][j],f[a][b]+1)

        初始化所有的f[i][j]=−1f[i][j]=-1，然后对于每一个点(i,j)(i,j)，跑一遍DFS，加一个记忆化搜索的判断

        方法步骤

        1. 定义数据结构：

          • 使用二维数组 g 存储滑雪场的高度。
          • 使用二维数组 f 存储从每个点出发的最大路径长度，初始值设为 -1 表示尚未计算。

        2. DFS 函数：

          • 通过递归的方式计算以 (x, y) 为起点的最大路径长度。如果已经计算过（f[x][y] != -1），直接返回已存储的结果。
          • 否则，将路径长度初始化为 1（包括当前点）。
          • 检查四个方向（上、下、左、右），如果相邻点高度低于当前点，递归调用 DFS 计算相邻点的最大路径长度，并更新当前点的最大路径长度。

        3. 主函数：

          • 输入滑雪场的高度信息。
          • 对于每个点调用 DFS 函数，计算并更新最大路径长度。

        4. 输出结果：

          • 最后，输出所有点中找到的最长路径长度。
        if(f[i][j]!=-1){   //说明该点已经被访问过 直接返回
    return f[i][j];
}

        C++

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

const int N=210; // 定义最大数组大小
int g[N][N], n, m, f[N][N]; // g 存储高度, f 存储最大路径长度
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, 1, -1}; // 四个方向的偏移量

// 深度优先搜索函数
int dfs(int x, int y) {
    // 如果已经计算过，直接返回结果
    if(f[x][y] != -1) return f[x][y];
    f[x][y] = 1; // 当前点的路径长度至少为 1
    int t = 0; // 用于记录下方可达的最大路径长度

    // 遍历四个相邻的方向
    for(int i = 0; i < 4; i++) {
        int a = dx[i] + x, b = dy[i] + y; // 计算相邻点的坐标
        // 检查边界条件和高度条件
        if(a < 0 || a >= n || b < 0 || b >= m || g[a][b] >= g[x][y]) continue;
        // 递归 DFS 计算相邻点的路径长度
        t = max(t, dfs(a, b));
    }
    
    f[x][y] += t; // 更新当前点的路径长度
    return f[x][y]; // 返回当前点的最大路径长度
}

int main() {
    cin >> n >> m; // 输入滑雪场的行列数
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> g[i][j]; // 输入每个点的高度
        }
    }
    
    memset(f, -1, sizeof f); // 初始化路径长度数组
    int res = 1; // 记录最长路径，初始为 1

    // 对每个点调用 DFS 计算最大路径长度
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            res = max(res, dfs(i, j)); // 更新最长路径
        }
    }
    
    cout << res << endl; // 输出结果
    return 0;
}

        Java

        import java.util.*;

public class Main {
    // 定义滑雪场的高度数组和记忆化数组
    static int[][] g = new int[210][210]; // g[i][j]表示(i,j)点的高度
    static int[][] f = new int[210][210]; // f[i][j]表示从(i,j)开始的最大滑雪路径长度
    static int n, m; // n为行数，m为列数
    // 四个方向的偏移量，分别是上、下、左、右
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, 1, -1};

    // 深度优先搜索函数
    static int dfs(int x, int y) {
        // 如果该点的最大路径长度已经计算过，直接返回
        if (f[x][y] != -1) return f[x][y];
        f[x][y] = 1; // 初始化路径长度为1（包括当前点）
        int t = 0; // 用于记录可达的最大路径长度

        // 遍历四个相邻的方向
        for (int i = 0; i < 4; i++) {
            int a = dx[i] + x, b = dy[i] + y; // 计算相邻点的坐标
            // 检查边界条件和高度条件，确保只向低于当前高度的点滑动
            if (a < 0 || a >= n || b < 0 || b >= m || g[a][b] >= g[x][y]) continue;
            // 递归调用DFS函数计算相邻点的最大路径长度
            t = Math.max(t, dfs(a, b));
        }

        // 更新当前点的最大路径长度
        f[x][y] += t;
        return f[x][y]; // 返回当前点的最大路径长度
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 创建输入扫描器
        n = sc.nextInt(); // 输入行数
        m = sc.nextInt(); // 输入列数
        // 输入每个点的高度
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                g[i][j] = sc.nextInt();
            }
        }

        // 初始化记忆化数组f为-1，表示尚未计算
        for (int i = 0; i < n; i++) {
            Arrays.fill(f[i], -1); // 将每一行的所有值设置为-1
        }

        int res = 1; // 记录最长路径长度，初始为1
        // 对每个点调用DFS函数计算最大路径长度
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                res = Math.max(res, dfs(i, j)); // 更新最长路径
            }
        }

        // 输出最长滑雪路径长度
        System.out.println(res);
    }
}

        Python3

        # 读取行数 n 和列数 m
n, m = map(int, input().split())
# 读取滑雪场的高度矩阵 g
g = [list(map(int, input().split())) for _ in range(n)]
# 初始化记忆化数组 f，用于存储每个点的最大路径长度，初始值为 -1
f = [[-1] * m for _ in range(n)]
# 定义四个方向的偏移量：上、下、左、右
dx, dy = [-1, 1, 0, 0], [0, 0, 1, -1]

# 深度优先搜索函数
def dfs(x, y):
    # 如果该点的最大路径长度已经计算过，直接返回
    if f[x][y] != -1:
        return f[x][y]
    
    # 初始化当前点的路径长度为 1（包括当前点）
    f[x][y] = 1
    t = 0  # 用于记录可达的最大路径长度

    # 遍历四个相邻的方向
    for i in range(4):
        a, b = dx[i] + x, dy[i] + y  # 计算相邻点的坐标
        # 检查边界条件和高度条件，确保只向低于当前高度的点滑动
        if a < 0 or a >= n or b < 0 or b >= m or g[a][b] >= g[x][y]:
            continue  # 跳过不满足条件的点
        
        # 递归调用 DFS 函数计算相邻点的最大路径长度
        t = max(t, dfs(a, b))
    
    # 更新当前点的最大路径长度
    f[x][y] += t
    return f[x][y]  # 返回当前点的最大路径长度

res = 1  # 记录最长路径，初始为 1
# 对每个点调用 DFS 函数计算最大路径长度
for i in range(n):
    for j in range(m):
        res = max(res, dfs(i, j))  # 更新最长路径

# 输出最长滑雪路径长度
print(res)
        • 1

        2023.10.12-秋招-留学生-第二题-塔子哥的滑雪冒险

        Information

        ID
        67
        Time
        1000ms
        Memory
        256MiB
        Difficulty
        6
        Tags
        # Submissions
        127
        Accepted
        38
        Uploaded By
        1. About
        2. Contact Us
        3. Privacy
        4. Terms of Service
        5. Copyright Complaint
        6. Language
        7. Legacy mode
        8. Theme
        2. 湘ICP备2023007293号
        3. Worker 0, 32ms
        4. Powered by Hydro v4.14.1 Community