给定一个大小为 n×n 的非负整数矩阵 grid
,其中 grid[i][j]
表示通过位置 [i,j] 所需的代价,若 grid[i][j] = 0
则该位置为障碍物,车辆无法通过。
假定有两辆车在给定一个n×n的非负整数矩阵地图grid中行驶,地图左上角位置为[0,0]。我们简化车辆行驶的方式,每辆车可以从一个坐标行驶到相邻 (上下左右)的另一个坐标,并且经过的每个位置都会产生代价,包括起始位置的代价。其中grid[i][j]表示通过网格位置[i,j] 所需的代价。矩阵中,grid[i][j]等于0表示该位置为障碍物,车辆无法通过。两辆车约定好需要在地图中快速相遇进行货物交接。
两辆车相遇的定义为:两辆车最终分别停在相邻的网格位置(上下或左右相邻),并且路径可达。
两辆车相遇所需的代价定义为:两辆车到达各自相遇位置所需代价中的较大值。
注意:路径代价包含车辆的起始位置位置的代价;行驶过程中,车辆可以停在某一个网格位置上,两辆车无需同步行驶。
求两辆车可以相遇需要的最小代价,如果无法相遇则返回−1。
第一行输入是一个整数n,代表地图grid[n][n]的大小,即n行n列大小的地图。
后续每一行代表地图中通过每个网格位置所需的时间信息,即grid[n][n]的每一行的元素值。
假设初始状态两辆车分别从左上角[0,0]和右下角 [n−1,n−1] 出发,左上角的车只能向右或向下移动,右下角的车只能向上或向左移动。
参数取值范围:
一个整数,表示两辆车相遇的最小代价;如果两车无法相遇(例如都被障碍物阻挡),则返回−1。
输入
2
1 2
2 1
输出
3
第一行输入代表该地图大小是2,即2行2列的矩阵。
地图信息为:
grid[n][n]=
[[1,2],
[2,1]]
最快相遇的一种方案是:
第一辆车路径:[0,0]−>[0,1],所需代价:1+2=3
第二辆车路径:[1,1],所需代价:1
两辆车在下方矩阵中小括号标记状态相遇,需要代价是3(取两辆车各自代价的较大值3作为相遇的代价),所以返回3。
[[1,(2)],
[2,(1)]]
输入
3
1 2 3
1 2 3
1 2 3
输出
5
第一行输入代表该地图大小是3,即3行3列的矩阵。
地图信息为:
grid[n][n]=
[[1,2,3],
[1,2,3],
[1,2,3]]
最快相遇的一种方案是:
第一辆车路径:[e,0]−>[1,e]−>[2,0],所需代价:1+1+1=3 第二辆车路径:[2,2]−>[2,1],所需代价:5
两辆车在下方矩阵中小括号标记状态相遇,需要代价是5(取两辆车各自代价的较大值5作为相遇的代价),所以返回5。
[[1,2,3],
[1,2,3],
[(1),(2),3]]
输入
3
1 0 3
1 0 3
1 0 3
输出
-1
第一行输入代表该地图大小是3,即3行3列的矩阵。
地图信息为
grid[n][n]=
[[1,0,3],
[1,0,3],
[1,0,3]]
由于地图中的障碍物,使得两辆车无法相遇,所以返回−1。