OD C卷 - 寻找最优的路测线路

本文主要是介绍OD C卷 - 寻找最优的路测线路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

寻找最优的路测线路（200）

• 给定一个m行、n列的数组（路线网络），每个值代表当前位置的信号质量，越大信号越好；
• 从 [0, 0] 到 [m-1, n-1]位置的路线中，最小值代表当前路线的评分，如8->4->5->9的评分为4；
• 每个位置可以走向上下左右四个方向，不能对角；
• 找出一个网络中的最优路线的评分；
  输入描述：
  第一行输入行数m;
  第二行输入列数n;
  第三行开始，每行为信号值s；
  1< m,n <20
  1 < s < 65535
  输出描述：
  最优路线的评分

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

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

思路：

• 二分法，取值 mid =（low+high）// 2
• mid从大到小，以当前值走DFS遍历，能找都一条线路，则停止，并输出mid

def dfs(x, y, mid):global row, col, matrix, visited# 最后一个位置if x == row - 1 and y == col - 1:return Trueelif matrix[x][y] < mid:return Falseelse:visited[x][y] = 1 # 标记已访问dirtection = [-1, 0, 1, 0, -1]# 四个方向for i in range(4):new_x = x + dirtection[i]new_y = y + dirtection[i + 1]if new_x >= 0 and new_x < row and new_y >= 0 and \new_y < col and visited[new_x][new_y] == 0 and matrix[new_x][new_y] >= mid:# 继续深度优先if dfs(new_x, new_y, mid):return Truereturn Falserow = int(input().strip())
col = int(input().strip())
matrix = []
visited = []
for i in range(row):matrix.append(list(map(int, input().strip().split())))visited.append([0 for _ in range(col)])# 二分法 + BFS
left = 0
right = 65535
while left < right:mid = (left + right) // 2   # 从大值到小值 逐渐变化# 初始化 visitedfor i in range(row):for j in range(col):visited[i][j] = 0if dfs(0, 0, mid):left = midelse: # 不满足需要减小right = mid - 1print(left)

这篇关于OD C卷 - 寻找最优的路测线路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---