• [1673] 迷宫问题

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • Alex的猫咪不小心走进了迷宫,Alex为了心爱的猫咪,决定进入迷宫去解救他的猫咪。

    已知猫咪坐标为(n - 1, m - 1),Alex坐标为(0, 0),Alex只能往下或者往右走,且不能走出迷宫,迷宫的大小为n*m,迷宫每个格子上都有一个数字x,如果x大于0,说明Alex走到这个格子上后,血量增加x;反之血量减少x,要求不论在哪个格子,血量都至少大于等于1,且血量没有上限,问,如果Alex要成功从(0,0)走到(n - 1, m - 1),需要的初始血量最少应该是多少?


  • 输入
  • 先输入 T,说明有T组数据。
    接下来T个case
    每个case上
    输入 n, m(迷宫的大小)(1 <= n, m <= 1000)
    接下来输入迷宫,保证每格都是整型。
    且每个数字绝对值都小于等于100

  • 输出
  • 输出Alex 最小需要的初始血量值。
  • 样例输入
  • 2
    3 3
    2 -1 1
    -1 0 -1
    -1 -1 3
    3 3
    3 -9 7
    -3 -2 -8
    0 -1 0
    
  • 样例输出
  • 1
    2
    
  • 提示
  • 来源
  • Alex
  • 操作

显示春菜