33OJ
登录 注册

#P17836. 二维市闯关

    ID: 20512 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 显示难度普及 上传者: 标签>上海O2优化最短路2026高校校赛

二维市闯关

题目描述

你现在正身处二维市,并希望离开时留有的金币数值尽可能大。(金币在二维市中是一种虚拟货币,值可以为负数)。

二维市的地图可以抽象为一个 n×mn \times m 的矩阵,位于坐标 (i,j)(i,j) 时能收集 ai,ja_{i,j} 个金币。(ai,ja_{i,j} 可以为负数,意味着来到这个位置会让你的金币数减少)。当离开某位置后,此位置的金币数量会重新刷新。

初始你位于起点 (1,1)(1,1),每步可以移动到上、下、左、右相邻且在地图内的位置,最终需要在若干步后从 (n,m)(n,m) 离开。(每个位置可以重复经过多次,包括终点 (n,m)(n,m))。

请你求出,离开时留有的金币数值最大是多少?

输入格式

第一行两个正整数 nn 和 mm(1≤n×m≤1051 \leq n \times m \leq 10^5),表示地图的大小。

而后 nn 行,每行 mm 个数,表示 ai,ja_{i,j}(−109≤ai,j≤109-10^9 \leq a_{i,j} \leq 10^9)。

输出格式

如果通过某种移动方式,可以使最终持有的金币数量任意大,请输出 Infinity\texttt{Infinity}。

否则输出一个整数,表示离开时留有的最大金币数值。

2 2
1 3
-2 4
Infinity
3 3
-4 -3 -2
1 -1 0
-3 -1 -1
-5

提示

对于样例二:

按照 $(1,1) \rightarrow (2,1) \rightarrow (2,2) \rightarrow (2,3) \rightarrow(3,3)$ 的路径可以在离开时留有 −5-5 个金币,可以证明这是最大值。