/ / 题库 /

矩阵取数(Easy Version)

矩阵取数(Easy Version)

测试数据来自 nnu_contest/1264

矩阵取数(Easy Version)

时间限制:1s

空间限制:64MB

题目描述

给定正整数\(n,m\),在\(n*m\)的矩阵中取若干个数字,但任意两个取出的数字在矩阵中的位置不能相邻。

(若A位置与B位置在矩阵的同一行,但列号相差1,或它们在同一列,但行号相差1,则称它们相邻。

注意:左上方、左下方、右上方、右下方不算相邻。)

问:取出数字的最大和是多少?

输入格式

第一行两个整数\(n,m\),表示矩阵大小。

接下来\(n\)行每行\(m\)个整数,表示这个矩阵

输出格式

一个整数,表示答案。

样例输入1

3 3
1 3 5
2 4 1
2 3 5

样例输出1

17

样例1解释

选第一行1,5,第二行4,第三行2,5

可以证明这是最大的情况。

样例输入2

3 3
10 7 6
4 15 2
3 33 1

样例输出2

49

样例2解释

10+6+33=49

样例输入3

5 5
1 4 12 7 2
9 23 1 4 11
12 3 7 2 7
92 15 44 3 1
10 7 8 2 20

样例输出3

212

样例输入4

6 2
8 3 
8 2 
8 1 
6 5 
2 10 
2 9 

样例输出4

34

数据范围及限制

\(1\le n,m\le 6\)

\(0<a_{ij}<10^4\)

信息

ID
2311
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者