#P1123. 取数游戏

    ID: 706 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>搜索枚举暴力深度优先搜索DFS

取数游戏

题目描述

一个N×MN \times M的由非负整数构成的数字矩阵,你需要在其中取出若干个数字,使得取出的任意两个数字不相邻(若一个数字在另外一个数字相邻88个格子中的一个即认为这两个数字相邻),求取出数字和最大是多少。

输入格式

第1行有一个正整数TT,表示了有TT组数据。

对于每一组数据,第一行有两个正整数NNMM,表示了数字矩阵为NNMM列。

接下来NN行,每行MM个非负整数,描述了这个数字矩阵。

输出格式

TT行,每行一个非负整数,输出所求得的答案。

3
4 4
67 75 63 10
29 29 92 14
21 68 71 56
8 67 91 25
2 3
87 70 85
10 3 17
3 3
1 1 1
1 99 1
1 1 1

271
172
99

提示

对于第1组数据,取数方式如下:

[67] 75 63 10

29 29 [92] 14

[21] 68 71 56

8 67 [91] 25

对于20%20\%的数据,N,M3N, M≤3

对于40%40\%的数据,N,M4N,M≤4

对于60%60\%的数据,N,M5N, M≤5

对于100%100\%的数据,N,M6,T20N, M≤6,T≤20