唐宋元明清

用户名：tangsong

访问量：1936

签　名：

一袋米要扛几楼

等　　级
排　　名	49216
经　　验	293
参赛次数	0
文章发表	4
年　　龄	23
在职情况	学生
学　　校
专　　业

　　自我简介：

宗之潇洒美少年，举觞白眼望青天，皎如玉树临风前。

TA的其他文章

P1005-题解（Java代码）
浏览：298

P1007-题解（Java代码）
浏览：250

吹哨传球-题解（Java代码）
浏览：525

你可能喜欢

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

P1004-题解（Java代码）

　　作者: 唐宋元明清　　　　发表时间：2020-05-06 20:34:37 浏览：316　|　评论：0　

原题链接：矩形滑雪场

记函数 **f(i, j)** 表示点 (i, j) 的最大滑雪距离，值为：
　　　　　　　**f(i, j) = max{周围比它低的点的滑雪距离} + 1**
比如，左边的点和下边的点比目标点低，
则　　　　　　f(i, j) = max{ f(i, j - 1), f(i + 1, j)} + 1

为了减少递归次数，对中间结果进行存储。

```java
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		
		Scanner scanner = new Scanner(System.in);
		
		int row = scanner.nextInt();
		int col = scanner.nextInt();
		int height[][] = new int[row][col];		// 高度矩阵
		for (int i = 0; i < height.length; i++) {
			for (int j = 0; j < height[0].length; j++) {
				height[i][j] = scanner.nextInt();
			}
		}
		scanner.close();
		
		int maxSkiingDis = 0;
		int[][] dis = new int[row][col];	// 滑雪距离矩阵，存储中间结果，减少递归次数
		for (int i = 0; i < height.length; i++) {
			for (int j = 0; j < height[0].length; j++) {
				maxSkiingDis = Math.max(maxSkiingDis, calSkiingDistance(height, i, j, dis));
			}
		}
		System.out.println(maxSkiingDis);
		
	}
	
	// 计算(i, j)点的最大滑雪距离
	private static int calSkiingDistance(int[][] height, int i, int j, int[][] dis) {
		// step1. 计算周围比它低的点的最大滑雪距离
		int leftPointDis = 0, rightPointDis = 0;
		int upPointDis = 0, downPointDis = 0;
		if (j > 0 && height[i][j - 1] < height[i][j]) {
			if (0 == dis[i][j - 1]) {
				calSkiingDistance(height, i, j - 1, dis);
			}
			leftPointDis = dis[i][j - 1];
		}
		if (j < height[0].length - 1 && height[i][j + 1] < height[i][j]) {
			if (0 == dis[i][j + 1]) {
				calSkiingDistance(height, i, j + 1, dis);
			}
			rightPointDis = dis[i][j + 1];
		}
		if (i > 0 && height[i - 1][j] < height[i][j]) {
			if (0 == dis[i - 1][j]) {
				calSkiingDistance(height, i - 1, j, dis);
			}
			upPointDis = dis[i - 1][j];
		}
		if (i < height.length - 1 && height[i + 1][j] < height[i][j]) {
			if (0 == dis[i + 1][j]) {
				calSkiingDistance(height, i + 1, j, dis);
			}
			downPointDis = dis[i + 1][j];
		}
		
		// step2. 计算当前点的最大滑雪距离
		int maxDis = Math.max(Math.max(leftPointDis, rightPointDis), Math.max(upPointDis, downPointDis));
		dis[i][j] = maxDis + 1;
		return dis[i][j];
	}
	
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

唐宋元明清

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C++代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

P1004-题解（Java代码）

评论区

精彩推荐

C二级辅导-等差数列（C语言代码）

矩形面积交（C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C二级辅导-进制转换（C语言代码）

数列排序（C语言代码）

C语言训练-尼科彻斯定理（C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

简单的a+b （C语言代码）

IP判断（C语言代码）

唐宋元明清

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C++代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

P1004-题解（Java代码）

评论区

精彩推荐

C二级辅导-等差数列 （C语言代码）

矩形面积交 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C二级辅导-进制转换 （C语言代码）

数列排序 （C语言代码）

C语言训练-尼科彻斯定理 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

简单的a+b （C语言代码）

IP判断 （C语言代码）

　　评论区

C二级辅导-等差数列（C语言代码）

矩形面积交（C语言代码）

C二级辅导-进制转换（C语言代码）

数列排序（C语言代码）

C语言训练-尼科彻斯定理（C语言代码）

IP判断（C语言代码）