思路

• 设 $need[i][j]$ 表示“到达 $(i,j)$ 这一刻之前必须至少有多少积分”，这样在加上当前格子 $a_{ij}$ 后，仍能保证后续一路存活并最终到达终点，同时过程中积分始终 $>0$。

• 终点处有

  $$need[N][M]=\max{1,1-a_{N,M}}$$

  因为到达终点后不再前进，但本格加上后仍需保持积分 $\ge 1$。

题目内容

这是一个经典的 $N$ 行 $M$ 列的二维迷官，每个格子有一个整数，代表这个格子的“奖励”或“惩罚”。

玩家从最左上角的格子 $(1,1)$ 出发，目的地是最右下角的格子 $(N,M)$，并且玩家只能向右或向下走玩家在游戏开始时积分为 $0$ ，并且每到一个格子(包括起始位置和终点位置)，都需要把当前积分加上这个格子对应的整数(显然，若整数为正就是“奖励”，若为负就是“惩罚”)。当玩家在任意时刻积分为 $0$ 或负数时，就输掉了游戏。