BZPRO
#2704. 旅游
内存限制：128 MiB
时间限制：20 Sec
提交
提交记录
讨论
题目描述
有一个
N*M
的格子地图，地图上的格子有些是障碍，不能通过，有些不是障碍，有一个快乐程度，从每个格子可以移向上下左右四个格子。
小月想从
[1,1]
格出发，旅游一些格子并回到
[1,1]
格，旅游的快乐程度等于经过的所有格子的快乐程度之和，小月想使得旅游的快乐程度之和尽可能大。
注意：
1.
保证
[1,1]
格不是障碍
2.
除
[1,1]
格外不能重复走过同一格
3.
[1,1]
格的快乐程度只算一次
4.
快乐程度可能是负数
5.
若不能从
[1,1]
格出去并回来，则小月不会进行此次旅游。
6.
若旅游的快乐程度为负数，则小月不会进行此次旅游。
7.
若小月不会进行旅游，则旅游快乐程度为
0
。
输入格式
第一行两个正整数
N
，
M
。
接下来
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。
BZPRO