首页 > 试题广场 >

滑雪

[编程题]滑雪

热度指数：4012 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个 $n \times m \$ 的矩阵，矩阵中的数字表示滑雪场各个区域的高度，你可以选择从任意一个区域出发，并滑向任意一个周边的高度严格更低的区域（周边的定义是上下左右相邻的区域）。请问整个滑雪场中最长的滑道有多长？(滑道的定义是从一个点出发的一条高度递减的路线）。

(本题和矩阵最长递增路径类似，该题是当年NOIP的一道经典题)

数据范围： $1 \le n,m \le 100 \$ ，矩阵中的数字满足 $1 \le val \le 1000 \$

输入描述:

第一行输入两个正整数 n 和 m 表示矩阵的长宽。
后续 n 行输入中每行有 m 个正整数，表示矩阵的各个元素大小。

输出描述:

输出最长递减路线。

示例1

输入

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

输出

说明

从25出发，每次滑向周边比当前小 1 的区域。 25->24->23->22->......->1

算法知识视频讲解

C++

Spectre_

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

int dfs(vector<vector<int>> &arr, int n, int m, int i, int j, 
        int pre, vector<vector<int>> &dp) {
    if (i < 0 || i >= n || j < 0 || j >=m || arr[i][j] >= pre) return 0;
    if (dp[i][j] != -1) return dp[i][j];
    dp[i][j] = 1;
    dp[i][j] = max(dp[i][j], dfs(arr, n, m, i - 1, j, arr[i][j], dp) + 1);
    dp[i][j] = max(dp[i][j], dfs(arr, n, m, i + 1, j, arr[i][j], dp) + 1);
    dp[i][j] = max(dp[i][j], dfs(arr, n, m, i, j - 1, arr[i][j], dp) + 1);
    dp[i][j] = max(dp[i][j], dfs(arr, n, m, i, j + 1, arr[i][j], dp) + 1);
    return dp[i][j];
}

int main() {
    int n, m, res = 0;
    cin >> n >> m;
    vector<vector<int>> arr(n, vector<int>(m, 0)), dp(n, vector<int>(m, -1));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) cin >> arr[i][j];
    }
    // 时间复杂度O(N^2)，空间复杂度O(N)
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            res = max(res, dfs(arr, n, m, i, j, INT_MAX, dp));
        }
    }
    cout << res;
    return 0;
}

发表于 2022-11-02 10:06:28 回复(0)

Java

Sen🍓🍀

import java.util.Scanner;

// 回溯
public class Main {
    private static int res = 1; // 结果：初始1段
    private static boolean[][] visited; // 标记访问
    private static int[][] direction = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 方向

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        visited = new boolean[n][m];
        int[][] grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = in.nextInt();
            }
        }

        for (int i = 0; i < n; i++) { // [i,j]每个点都尝试起始点
            for (int j = 0; j < m; j++) {
                visited[i][j] = true;
                backtrack(grid, i, j, 1);
                visited[i][j] = false;
            }
        }
        System.out.println(res);
    }

    // 回溯
    private static void backtrack(int[][] grid, int x, int y, int cnt) {
        int n = grid.length, m = grid[0].length;
        for (int k = 0; k < 4; k++) {
            int i = x + direction[k][0], j = y + direction[k][1];
            if (i < 0 || i >= n || j < 0 || j >= m ||
                    visited[i][j] || grid[i][j] >= grid[x][y])
                continue;
            visited[i][j] = true;
            res = Math.max(res, cnt + 1);
            backtrack(grid, i, j, cnt + 1); // 下一层
            visited[i][j] = false;
        }
    }
}

发表于 2025-03-25 16:23:34 回复(0)

Python3

实习_机器学习_广东或四川_5月中可入职

n,m = map(int, input().split())

# print(n,m)

grid = []

for _ in range(n):

grid.append(list(map(int,input().split())))

# print(grid)

memo = [[0]*m for _ in range(n)] # 记忆化搜索，当查到这个memo矩阵的时候直接将之前已经计算好的距离拿过来用

directions = [[-1,0],[1,0],[0,-1],[0,1]]

def dfs(x,y):

if memo[x][y] != 0: # 当查到这个memo矩阵的时候直接将之前已经计算好的距离拿过来用

return memo[x][y]

maxlen = 1

for direction in directions:

newx, newy =x+direction[0],y+direction[1]

if 0<=newx<n and 0<=newy<m and grid[newx][newy]<grid[x][y]:

maxlen = max(maxlen, dfs(newx,newy)+1)

return maxlen

res = 0

for i in range(n):

for j in range(m):

res = max(res, dfs(i,j))

print(res)

发表于 2025-03-24 15:03:43 回复(0)

牛客519895393号

#include <iostream>
#include <vector>

using namespace std;

int dfs(vector<vector<int>>& matrix,vector<vector<int>>& dp,int x,int y,int pre) {
    if(x < 0 || y < 0||x >= matrix.size()||y >= matrix[0].size()||matrix[x][y] >= pre) {
        return 0;
    }

    int l1 = dfs(matrix,dp,x+1,y,matrix[x][y]);
    int l2 = dfs(matrix,dp,x-1,y,matrix[x][y]);
    int l3 = dfs(matrix,dp,x,y+1,matrix[x][y]);
    int l4 = dfs(matrix,dp,x,y-1,matrix[x][y]);

    dp[x][y] = 1+max(max(l1,l2),max(l3,l4));

    return dp[x][y];
}

int main() {
//dp[i][j] 代表从原来矩阵ij出发的最长距离
    int n,m;
    cin >> n >> m;
    vector<vector<int>> matrix(n,vector<int>(m));
    vector<vector<int>> dp(n,vector<int>(m,0));

    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            cin >> matrix[i][j];
        }
    }

    int res = 1;

    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++) {
            res = max(res,dfs(matrix,dp,i,j,matrix[i][j]+1));
        }
    }

    cout << res << endl;

}
// 64 位输出请用 printf("%lld")

发表于 2024-09-09 15:54:57 回复(0)

愉快的大白菜不讲武德

import java.util.*;

class Main {

public static void main(String[] args) {
DP18();

}

static int[][] dp;
static int[][] matrix;
static int[][] path;

static int N, M;

static void DP18() {
Scanner in = new Scanner(System.in);
N = in.nextInt();
M = in.nextInt();

matrix = new int[N][M];
dp = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
matrix[i][j] = in.nextInt();
}
}
path = new int[N][M];

int max = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
dp[i][j] = searchMatrix(j, i, path);
max = Math.max(max, dp[i][j]);
}
}
//printDp();
System.out.println(max);
}
static void printDp() {
int n = dp.length; //行优先, 表示多少行
int m = dp[0].length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.print(dp[i][j]);
if (j < m - 1) System.out.print(" ");
}
System.out.println();
}
}

//搜索矩阵, 返回最大值的那个写入dp中..
//如果遇到dp 对应的有数据那么直接引用, 不然继续搜索.
//如果还有下一个返回 1+ searchMatrix(), 搜索的时候, 避免碰到已经经过的路径,把路径作为参数写入其中.
//确保 x, y 不超出边界.
static int searchMatrix(int x, int y, int[][] path) {
if (path[y][x] == 1) return 0; //来过就不整了.
if (dp[y][x] > 0) {
return dp[y][x];
}

path[y][x] = 1; //路径中加上此坐标, 表示来过..

int result = 1;
//四个方向... 如果有较小值那么继续..
//上
if (y - 1 >= 0 && matrix[y][x] > matrix[y - 1][x]) {
result = Math.max(result, 1 + searchMatrix(x, y - 1, path));
}
//下
if (y + 1 < N && matrix[y][x] > matrix[y + 1][x]) {
result = Math.max(result, 1 + searchMatrix(x, y + 1, path));
}
//左
if (x - 1 >= 0 && matrix[y][x] > matrix[y][x - 1]) {
result = Math.max(result, 1 + searchMatrix(x - 1, y, path));
}
//右
if (x + 1 < M && matrix[y][x] > matrix[y][x + 1]) {
result = Math.max(result, 1 + searchMatrix(x + 1, y, path));
}
path[y][x] = 0; //返回的时候. 路径一起回退.
return result; //搜索结束.
}

}

发表于 2022-11-18 16:42:21 回复(0)

牛客419656984号

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

int n=in.nextInt(),m=in.nextInt();

int[][] arr=new int[n][m];

for(int i=0;i<n;i++){

for(int j=0;j<m;j++){

arr[i][j]=in.nextInt();

}

int[][] dp=new int[n][m];

int res=1;

for(int i=0;i<n;i++){

for(int j=0;j<m;j++){

res=Math.max(res,dfs(i,j,arr,dp,1005));

}

System.out.println(res);

}

public static int dfs(int i,int j,int[][] arr,int[][] dp,int pre){

if(i < 0 || i == arr.length || j < 0 || j == arr[0].length)//边界情况

return 0;

if(pre<=arr[i][j]) return 0;

if(dp[i][j]!=0) return dp[i][j];

int cur=0;

cur=Math.max(cur,dfs(i-1,j,arr,dp,arr[i][j]));

cur=Math.max(cur,dfs(i+1,j,arr,dp,arr[i][j]));

cur=Math.max(cur,dfs(i,j-1,arr,dp,arr[i][j]));

cur=Math.max(cur,dfs(i,j+1,arr,dp,arr[i][j]));

dp[i][j]=cur+1;

return dp[i][j];

}

发表于 2022-10-11 23:00:07 回复(0)

C++

pein531

这题数据有点弱，直接暴力递归竟然也过了，记忆化搜索就快一点点

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 105, M = 105;

int grid[N][M], dp[N][M], n, m;
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

int dfs(int x, int y, int prev) {
    if(x < 0 || x >= n || y < 0 || y >= m || grid[x][y] >= prev) return 0;
    if(dp[x][y] != -1) return dp[x][y];
    int path = 1;
    for(int i = 0; i < 4; i++) {
        path = max(path, 1 + dfs(x + dx[i], y + dy[i], grid[x][y]));
    }
    dp[x][y] = path;
    return path;
}

int main() {
    scanf("%d%d", &n, &m);
    memset(dp, -1, sizeof dp);
    for(int i = 0; i < n; i++) 
        for(int j = 0; j < m; j++)
            scanf("%d", &grid[i][j]);
    int ans = 1;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            ans = max(ans, dfs(i, j, 1001));
    printf("%d", ans);
    return 0;
}

发表于 2022-07-07 10:47:17 回复(0)

C++