交大OJ-1063-小M爱滑雪 | code_nie's blog

交大OJ-1063-小M爱滑雪

交大OJ-1063-小M爱滑雪

1,解题思路

本来以为可以用动态规划,后来发现方向会向四面八方延伸,所以暂时想不出动态规划的方法,用递归解决了。

2,解题注意点

  1. 别像我一样把地形的高度与滑行的长度的数组弄混了……不知道我写代码时是怎么想的……
  2. 还有一个注意点,交大的OJ是没法用INT_MAX的,所以需要在程序的头部进行宏定义,否则会编译错误。

3,解题代码

这道题现在这个思路可能比较耗时,有更好的思路会继续写的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

#include <cstdio>
#include <iostream>
#include <vector>
#define MAX 0x7fffffff
using namespace std;

// 全局变量
int row, column;
vector<vector<int> > nums, lengthToken;

int getLength(int row, int column)
{
int height = nums[row][column];
int left = 0, right = 0, up = 0, down = 0;

if (nums[row][column - 1] < height) {
if (lengthToken[row][column - 1] == -1) {
left = getLength(row, column - 1);
}
else {
left = lengthToken[row][column - 1];
}
}

if (nums[row][column + 1] < height) {
if (lengthToken[row][column + 1] == -1) {
right = getLength(row, column + 1);
}
else {
right = lengthToken[row][column + 1];
}
}
if (nums[row - 1][column] < height) {
if (lengthToken[row - 1][column] == -1) {
up = getLength(row - 1, column);
}
else {
up = lengthToken[row - 1][column];
}
}
if (nums[row + 1][column] < height) {
if (lengthToken[row + 1][column ] == -1) {
down = getLength(row + 1, column);
}
else {
down = lengthToken[row + 1][column];
}
}
height = 0;
for (int l : {left, right, up, down}) {
height = (height > l) ? height : l;
}
height++;
lengthToken[row][column] = height;
return height;
}

int getMaxLength()
{
int maxLength = 0;
for (int i = 1; i <= row; i++) {
for (int j = 1; j <= column; j++) {
if (lengthToken[i][j] == -1) {
// have no result
getLength(i, j);
}
// already result
maxLength = (maxLength > lengthToken[i][j]) ? maxLength : lengthToken[i][j];
}
}
return maxLength;
}

int main()
{
scanf("%d %d", &row, &column);
nums = vector<vector<int>>(row + 2, vector<int>(column + 2));
lengthToken = vector<vector<int>>(row + 2, vector<int>(column + 2, -1));

// nums 就是滑雪场

for (int i : {0, row + 1}) {
for (int j = 0; j < column + 2; j++) {
nums[i][j] = MAX;
}
}
for (int j : {0, column + 1}) {
for (int i = 0; i < row + 2; i++) {
nums[i][j] = MAX;
}
}

// 滑雪场创建完毕

for (int i = 1; i <= row; i++) {
for (int j = 1; j <= column; j++) {
scanf("%d", &nums[i][j]);
}
}
// get Data

/*for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < nums[0].size(); j++) {
cout << nums[i][j] << " ";
}
cout << endl;
}*/
// 数据输入完毕

int result = getMaxLength();
// 得到结果

printf("%d", result);
return 0;
}