SP16283 TAP2013I - Treasure Island

寻找加勒比海岛屿上被海盗隐匿于数个世纪前的宝藏从来都不是一件容易的事，更难的是能活着讲述这段探险的故事。因为众所周知，海盗拥有的超自然力量会用来诅咒那些未经授权而盗取宝藏的人。 在最强大的海盗中，有一种被广泛流传并且让人心生敬畏的诅咒——「致命迷雾」。每当有人发现海盗的宝藏，这种诅咒会让有毒的迷雾从地面蔓延开来，直到整个岛屿都被覆盖住。任意被迷雾碰触到的生物都会立刻毙命，这对于刚刚找到宝藏的人来说是最不愿面对的局面。唯一的自救途径是立刻返回船上，在路上确保仅走过还未被迷雾笼罩的区域，并带着能够抢救出的部分宝藏迅速撤离。我们的问题是，如何在保证返回船上生存的前提下，计算出可以用来采集宝藏的最大时间。 为了简化问题，我们将岛屿视为一个由 **R** 行 **C** 列构成的网格，其中第 **i** 行第 **j** 列的单元格高于海平面的高度为 **H $ _{ij} $** 米。假设宝藏总是被藏在第 **1** 行第 **1** 列的单元格中，因为那是离唯一能停泊船只的位置，也就是第 **R** 行第 **C** 列的单元格最远的地方。一旦发现宝藏，致命迷雾会从海平面迅速升起，且每秒上升一单位高度，因此在 **t** 秒后，不能处于任何高度小于或等于 **t** 的单元格中。要返回船上，你只能从一个单元格移动到相邻的共享边界的单元格，也就是说，如果目前在某个单元格，则只能水平移动到同一行的相邻单元格，或垂直移动到同一列的相邻单元格，而不能对角线移动或越过岛屿边界。每次移动需要花费整整一秒钟。

第一行包含两个整数 **R** 和 **C**，分别表示岛屿网格的行数和列数，网格至少由两个单元格组成（$1 \leq R, C \leq 500$ 且 $R \times C \geq 2$）。接下来的 **R** 行，每行包含 **C** 个值。第 **i** 行的第 **j** 个值为一个整数 **H $ _{ij} $** ，表示第 **i** 行第 **j** 列单元格的高度（$1 \leq H $ _{ij} $ \leq 10^6$ 对于所有的 $i = 1, \ldots, R$ 和 $j = 1, \ldots, C$）。

输出一个整数，表示在不被致命迷雾触及的情况下，能够用以收集宝藏的最大时间（秒）。如果即便在发现宝藏后立即返回也无法安全到达船上，则输出 **-1**。

$1 \leq R, C \leq 500$，且 $R \times C \geq 2$，$1 \leq H_{ij} \leq 10^6$。 **本翻译由 AI 自动生成**