从左列到右列找出矩阵的最大总和路径？

 

杰夫喜欢玩游戏，贪吃蛇（诺基亚时代的老游戏）是他的最爱之一。 然而，在玩过饕s蛇多次后，他终于厌倦了原来的规则。 为了给这款老游戏带来新的挑战，杰夫推出了新的规则：

  • 地面是一个网格，有n行m列（1 <= n，m <= 500）。

  • 每个单元格包含一个值v（-1 vi 99999），如果v是-1，那么这个单元格被阻塞，并且s≤≤≤不能通过，否则，当snake访问这个单元格之后，你可以得到v点。

  • 蛇可以从沿着该地面的左边界的任何单元开始并行进，直到它最终停止在右边界的一个单元处。

  • 在这次旅行中，蛇只能上/下/右，并且只能访问每个单元格一次。 特别案例 ：

    • 一个。 即使在左边界和右边界，蛇也可以上下移动。

    湾 当蛇位于一列的顶部单元格时，它仍然可以上升，这要求玩家支付所有当前点数，然后蛇将被传送到该列的底部单元格，反之亦然。

    创建这样一款新游戏后，杰夫很困惑如何获得最高分。 请帮他写一个程序来解决这个问题。 输入第一行包含两个整数n（行）和m（列），（1 <= n，m <= 500），由一个空格分隔。 接下来n行描述网格。 每行包含m个整数vi（-1 vi 99999）≤≤vi = -1表示单元格被阻塞。 输出输出您可以获得的最高分数。 如果蛇不能到达右侧，则输出-1。

    输入：

    4 4

    -1 4 5 1

    2 -1 2 4

    3 3 -1 3

    4 2 1 2

    输出：

    23

    我已经解决了这个问题，但问题是你没有尝试过。如果你会尝试，这里的每个人都会帮助你。 不要仅仅复制和粘贴，而是写在你被卡住的地方。

    链接地址: http://www.djcxy.com/p/63843.html

    上一篇: Find the maximum sum path of a matrix from left column to right column?

    下一篇: Color Grid algorithm