6704: BZOJ2704:旅游

Memory Limit:128 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

有一个N*M的格子地图,地图上的格子有些是障碍,不能通过,有些不是障碍,有一个快乐程度,从每个格子可以移向上下左右四个格子。 小月想从[1,1]格出发,旅游一些格子并回到[1,1]格,旅游的快乐程度等于经过的所有格子的快乐程度之和,小月想使得旅游的快乐程度之和尽可能大。 注意: 1.      保证[1,1]格不是障碍 2.      [1,1]格外不能重复走过同一格 3.      [1,1]格的快乐程度只算一次 4.      快乐程度可能是负数 5.      若不能从[1,1]格出去并回来,则小月不会进行此次旅游。 6.      若旅游的快乐程度为负数,则小月不会进行此次旅游。 7.      若小月不会进行旅游,则旅游快乐程度为0


输入格式

第一行两个正整数NM 接下来N行,每行M个整数,第i行第j列的数为a[i][j]。当a[i][j]=0时表示此格是障碍,否则表示快乐程度。


输出格式

仅一行一个数,表示最大的旅游快乐程度。


样例输入

3 3
1 9 -1
-7 0 8
-1 -1 -1

样例输出

7

提示


【数据规模和约定】
100%的数据中:N,M<=12,-10000<=a[i][j]<=10000。


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: