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 resultif(step_count>result):result = step_countvisited[x][y] = 1i=1while(True):if(i>=5):breakelse :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] == 1or 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+=1continuedfs(xx, yy, step_count + 1, not flag)i+=1visited[x][y] = 0for i in range(m):for j in range(n):dfs(i,j, 0, True)dfs(i,j, 0, False)
print(result)