题目内容

假定有两辆车在给定一个$n×n$的非负整数矩阵地图$grid$中行驶，地图左上角位置为$[0,0]$。我们简化车辆行驶的方式，每辆车可以从一个坐标行驶到相邻 (上下左右)的另一个坐标，并且经过的每个位置都会产生代价，包括起始位置的代价。其中$grid[i][j]$表示通过网格位置$[i,j]$ 所需的代价。矩阵中，$grid[i][j]$等于$0$表示该位置为障碍物，车辆无法通过。两辆车约定好需要在地图中快速相遇进行货物交接。

两辆车相遇的定义为:两辆车最终分别停在相邻的网格位置(上下或左右相邻)，并且路径可达。

两辆车相遇所需的代价定义为:两辆车到达各自相遇位置所需代价中的较大值。

注意:路径代价包含车辆的起始位置位置的代价;行驶过程中，车辆可以停在某一个网格位置上，两辆车无需同步行驶。

题解

题面描述

给定一个大小为 $n\times n$ 的非负整数矩阵 grid，其中 grid[i][j] 表示通过位置 $[i,j]$ 所需的代价，若 grid[i][j] = 0 则该位置为障碍物，车辆无法通过。

• 第一辆车从 $[0,0]$ 出发，只能向右或向下移动；
• 第二辆车从 $[n-1,n-1]$ 出发，只能向上或向左移动；
• 任一车辆经过的每个位置（包括起始位置）都会产生对应的代价；
• 两辆车“相遇”定义为：它们最终分别停在一对相邻（上下或左右相邻）的网格位置上，且各自路径都可达；