OD C卷 - 中庸行者

中庸行者 （200）

• 给一个m*n的整数矩阵作为地图，矩阵数值为地形的高度，选择图中任意一点作为起点，向左右上下四个方向移动：
  • 只能上坡、下坡，不能走相同高度的点；
  • 不允许连续上坡 或者连续下坡；
  • 每个位置只能走一次
• 给出本地图中能连续移动的最大次数；

输入描述：
输入row, col
后续输入地图数据
输出描述：
能连续移动的最大次数

示例1
输入：
2 2
1 2
4 3
输出：
3

示例2
输入：
3 3
1 2 4
3 5 7
6 8 9
输出：
4

思路：

• DFS + visited控制
• flag 表示上一步是上坡还是下坡

 
params = [int(x) for x in input().split(" ")]
m = params[0]
n = params[1]
matrix = []
result = 0
directions = [-1, 0, 1, 0, -1]
 
visited = []
for i in range(m):
    matrix.append([int(x) for x in input().split(" ")])
    visited.append([0 for i in range(n)])
            
        
 
def dfs(x, y, step_count, flag) :
    global result
    if(step_count>result):
        result = step_count
    visited[x][y] = 1
    i=1
    while(True):
        if(i>=5):
            break
        else :
            xx = x + directions[i- 1]
            yy = y + directions[i]
            if (xx < 0 or yy < 0 or xx >= m or yy >= n or visited[xx][yy] == 1
                or matrix[xx][yy] == matrix[x][y] or ((flag and matrix[xx][yy] > matrix[x][y]) or (not flag and matrix[xx][yy] < matrix[x][y]))) :
                i+=1
                continue
            
            dfs(xx, yy, step_count + 1, not flag)
        
        i+=1
    visited[x][y] = 0
 
 
for i in range(m):
    for j in range(n):
        dfs(i,j, 0, True)
        dfs(i,j, 0, False)
print(result)
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