题解

题目描述

小华设计了一款简单的水果忍者游戏，游戏中存在一个 m*n 的网格，网格的每个单元格可能包含以下内容：

• 0：表示该单元格为空，不可滑动。
• -5：表示该单元格包含炸弹，滑动到炸弹上会失去 5 分。
• 正整数：表示该单元格包含水果，滑动到水果上会获得该水果的分数。

玩家可以从网格中的任意一个非空单元格出发，选择四个方向（上下左右）滑动到相邻的单元格，但不可滑动到空单元格（值为 0）。每个单元格只能滑动一次，滑动过的单元格会变为空单元格。

题目内容

小明设计了一款简单的水果忍者游戏，具体玩法如下:

(1)在m*n的网格，每个单元格中随机放着一个水果，或炸弹，或为空;为了方便表示，单元格中为整数，0表示空单元格，-5表示炸弹单元格，正整数表示水果单元格得分

(2)玩家可以滑动手指到水果或者炸弹上;滑到水果单元格会有对应加分，滑到炸弹单元格减5分，每个单元格被滑过后，将变为空单元格;不允许滑到空单元格上，滑到

(3)玩家可以从网格中任意一个非空单元格出发，每次从当前位置向上下左右四个方向滑;

请计算此局游戏最高得分

输入描述

第一行输入$m,n$两个正整数，表示整个网格行、列数，以空格分隔($m,n<=25$)

接下来依次输入$m$行，每行$n$个整数(取值范围:$0$，$-5$，正整数)，以空格分隔

输出描述

输出此局游戏最高得分

样例1

输入

3 3
0 6 0
5 8 7
0 9 0

输出

24 

说明

得分最高的滑动路径:$9->8->7$

样例2

输入

5 3
1 -5 7
2 0 6
3 4 5
-5 3 -5
9 0 20

输出

45

说明

得分最高的滑动路径:$20 ->-5 -> 3 -> 4 -> 5-> 6->7->-5 -> 1->2->3->-5-> 9$