迷宫取数
测试数据来自 nnu_contest/1286
迷宫取数
时间限制:4s
空间限制:64MB
题目描述
\(n*m\)的二维迷宫中,每个位置上都有一个数。
选择一条从起点\((1,1)\)到终点\((n,m)\)的路径, 且在路径中,每个点至多经过一次。
将路径上的数字相加,可以得到一个和。求此和的最大值。
输入格式
第一行两个正整数\(n,m\)。
接下来\(n\)行,每行\(m\)个整数,表示这个迷宫。
输出格式
一个整数,表示和的最大值。
样例输入1
4 4
1 7 10 4
-99 -99 3 -99
-20 110 -10 4
4000 1 -9999 3
样例输出1
3990
样例1解释
1 + (-99) + (-20) + 4000 + 1 + 110 + (-10) + 4 + 3 = 3990
样例输入2
2 5
1900 5112 270 -6250 2850
-3734 7803 425 8355 -46
样例输出2
23549
样例2解释
1900+5112+7803+425+8355-46 = 23549
数据范围及限制
共\(10\)组测试数据,每个测试点\( 15\)分。
对于前\(40\%\)的数据,\(a_{ij} = 1\)
对于\(100\%\)的数据,\(1\le n,m\le 6, -10000\le a_{ij}\le 10000\)。
信息
- ID
- 2330
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者