首页 > 试题广场 >

滑雪

[编程题]滑雪
  • 热度指数:2120 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个 的矩阵,矩阵中的数字表示滑雪场各个区域的高度,你可以选择从任意一个区域出发,并滑向任意一个周边的高度严格更低的区域(周边的定义是上下左右相邻的区域)。请问整个滑雪场中最长的滑道有多长?(滑道的定义是从一个点出发的一条高度递减的路线)。
(本题和矩阵最长递增路径类似,该题是当年NOIP的一道经典题)

数据范围: ,矩阵中的数字满足

输入描述:
第一行输入两个正整数 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

说明

从25出发,每次滑向周边比当前小 1 的区域。 25->24->23->22->......->1  
#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)
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)
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]!=0return 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)
这题数据有点弱,直接暴力递归竟然也过了,记忆化搜索就快一点点
#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)
深度优先搜索也可以
发表于 2022-04-05 15:58:30 回复(0)