2082. Star Adventure

单点时限: 3.0 sec

内存限制: 256 MB

The latest version of your favorite adventure game has just been released. On each level you search for stars that earn you points. Simply moving over a location containing stars allows you to acquire them. To help you on your journey, you are given an overhead map of the level in a vector . Each character in level describes the number of stars at that location. You begin in the upper left spot of the map (character 0 of element 0 of level). On the current stage you must move according to the following rules:

1) On the first pass you may only move downward or rightward each move (not diagonally) until you reach the lower right corner.

2) The second pass begins in the lower right corner where the first pass ended, and proceeds back to the beginning using only upward and leftward steps (not diagonal).

3) The final pass, like the first pass, begins in the upper left corner and proceeds to the lower right corner using only rightward and downward (not diagonal) steps.

Once the stars on a spot are claimed, they cannot be claimed again on a future pass.

-level will contain between 2 and 50 elements inclusive.

-Each element of level will contain between 2 and 50 characters inclusive.

-Each element of level will contain the same number of characters.

-Each character in each element of level will be a digit (‘0’ - ‘9’).

-Character 0 in element 0 of level will be ‘0’.

输入格式

First input two integer m,n,stand for there are m rows and n columns.then a vector stand

for the stars.

输出格式

Return the largest possible number of stars that can be acquired.

样例

Input
2 2
01
11
/*
10 10
0123456789
1123456789
2223456789
3333456789
4444456789
5555556789
6666666789
7777777789
8888888889
9999999999
7 3
012
012
012
012
012
012
012
*/
Output
3
/*
335
21
*/

3 人解决,6 人已尝试。

4 份提交通过,共有 29 份提交。

8.7 EMB 奖励。

创建: 11 年,11 月前.

修改: 2 年,5 月前.

最后提交: 9 年,3 月前.

来源: TC

题目标签