您的位置:首页 > 房产 > 家装 > OD C卷 - 寻找最优的路测线路

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

2024/12/25 0:05:34 来源:https://blog.csdn.net/weixin_45228198/article/details/141572770  浏览:    关键词: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)

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com