• [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
  • 操作

显示春菜