题解

题面描述

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

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

题目内容

假定有两辆车在给定一个$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]$ 出发，左上角的车只能向右或向下移动，右下角的车只能向上或向左移动。

参数取值范围:

• $2 <=n<=1000$
• $0 <= grid[i][j]<= 100$
• $grid[0][0]!= 0$
• $grid[n-1][n-1] != 0$

输出描述

一个整数，表示两辆车相遇的最小代价;如果两车无法相遇(例如都被障碍物阻挡)，则返回$-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)]]$

样例2

输入

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

输入

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$。