#8141. 网格行走 (path) 普及/提高−

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: CPP

题目描述

给你一个 的网格,网格中的每个格子中都写有一个整数,其中第 行第 列的格子上写有数字 。从 的所有整数都在网格中出现了恰好一次。

行第 列的格子,你现在需要从 走到 ,每次只能向右或向下走 (即从 走向 ),且不能走出网格。

定义一条行走路径的价值为所有经过的点上所写数字所构成集合的 。你需要求出所有 行走路径中价值的最大值。

定义一个集合的 为没有在集合中出现过的最小非负整数。

输入格式

第一行两个整数 ,表示网格的行数与列数。

接下来 行,每行 个整数,表示网格每个格子上所写的整数。

输出格式

一个整数,表示所有行走路径中价值的最大值。

样例

样例输入 1

2 3
1 2 4
3 0 5

样例输出 1

3

样例输入 2

1 5
1 3 0 4 2

样例输出 2

5

数据范围与提示

对于所有的数据,满足

  • 对于 的数据,满足
  • 对于另外 的数据,满足
  • 对于另外 的数据,无特殊限制。