提示: 欢迎访问OurACM平台。
Problem 1491 机器人测试

Accept: 107    Submit: 641
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

为了测试我们的足球机器人的性能,我们设计如下的测试方法:

将一个机器人放在一个n*n的矩形阵列的某个格子中,它每次可以向与它所处的格子相邻的4个格子中的任何一个移动。

在这个阵列的一些格子中,摆放着能量,机器人希望能够得到这些能量。但是,这个阵列中存在着两种障碍物,一种障碍物使得机器人无法向前移动进入这个格子;第二种障碍物机器人虽然可以通过,但是,通过这样一个障碍物的时候,它先前所吃到的所有的能量都将消失。你的任务是,对于给定的一个阵列以及它的描述,计算出这个机器人所能够获得的最大能量值。

Input

本题有多组输入数据,你必须处理到EOF为止

输入数据的第一行表示输入矩阵的维数n,接下来n行,每行有n个元素,给出一个n*n的矩阵(n<=1000)。这个矩阵中,0表示这个格子上什么都没有,-1是机器人开始的位置,-2表示的是第一种障碍物,-3表示的是第2种障碍物。其他非负整数值表示的是能量的数值。

Output

输出仅一行,表示机器人所能获得的最大能量。

我们保证最后结果在[0, 230]的范围内。

Sample Input

4 10000 -2 0 0 -2 1 -1 0 -3 -3 0 0 1000 -3 0 0

Sample Output

1000

Source

福州大学第四届程序设计竞赛

Submit  Back  Status  Discuss