#P17836. 二维市闯关
二维市闯关
题目描述
你现在正身处二维市,并希望离开时留有的金币数值尽可能大。(金币在二维市中是一种虚拟货币,值可以为负数)。
二维市的地图可以抽象为一个 的矩阵,位于坐标 时能收集 个金币。( 可以为负数,意味着来到这个位置会让你的金币数减少)。当离开某位置后,此位置的金币数量会重新刷新。
初始你位于起点 ,每步可以移动到上、下、左、右相邻且在地图内的位置,最终需要在若干步后从 离开。(每个位置可以重复经过多次,包括终点 )。
请你求出,离开时留有的金币数值最大是多少?
输入格式
第一行两个正整数 和 (),表示地图的大小。
而后 行,每行 个数,表示 ()。
输出格式
如果通过某种移动方式,可以使最终持有的金币数量任意大,请输出 。
否则输出一个整数,表示离开时留有的最大金币数值。
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)$ 的路径可以在离开时留有 个金币,可以证明这是最大值。