1377: 【中级组】采蘑菇

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：57 Solved：26

Description

       小熊采蘑菇是个小游戏，蘑菇分布在大小为 n * n 的网格 grid 两维数组中。每个单元格中的整数就表示这一单元格中的蘑菇数量；如果该单元格是空的，那么就是 0。为了采到最多的蘑菇，小熊需要按以下规则来采蘑菇：        (1) 小熊可以从网格中 任意一个有蘑菇的单元格出发或者是停止。        (2) 每进入一个单元，就采该单元格中的所有蘑菇。        (3) 小熊每次可以从当前位置向上下左右四个方向走。        (4) 每个单元格只能被采（进入）一次。        (5) 不得采（进入）蘑菇数目为 0 的单元格。
       请你通过选择不同的入口，找一条路径，输出能采到最多蘑菇的数量是多少。

输入：n=3, grid[][] = {(1,4,0},{3,7,9},{0,9,0}};
输出：25
解释：一种采到最多蘑菇的路线是：9 -> 7 -> 9。如下图示:
  
                       

Input

        第一行为一个数，为网格大小 n。第二行后面n行为n*n网格数据,  数据之间空格分隔。

Output

        输出一个正整数，表示采到蘑菇最多的数量是多少。

Sample Input Copy 

3
1 4 0
3 7 9
0 9 0

Sample Output Copy 

25

HINT

提示:

   2<=n<=10
   0<=grid[i]<=99