1288: 取数游戏
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:7
Solved:3
Description
现在有一个$N × M$的由非负整数构成的数字矩阵,需要在其中取出若干个数字,使得取出的任意两个数字不相邻(若一个数字在另外一个数字相邻$8$个格子中的一个即认为这两个数字相邻),求取出数字和最大是多少。
Input
第一行输入整数$N$和$M$,代表矩阵有$N$行$M$列;
接下来的$N$行,每行有$M$个正整数,数据以空格分开,代表数字矩阵。
接下来的$N$行,每行有$M$个正整数,数据以空格分开,代表数字矩阵。
Output
一行,输出最大的和。
Sample Input Copy
2 3
87 70 85
10 3 17
Sample Output Copy
172
HINT
$2 ≤ N, M ≤ 6$,$1 ≤ 矩阵中的数据 ≤ 1000$