一个 N× M 的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意两个数字不相邻（若一个数字在另外一个数字相邻 8 个格子中的一个即认为这两个数字相邻），求取出数字和最大是多少。
第一行有一个正整数 T （ 1≤ T≤ 20 ），表示了有 T 组数据。 对于每一组数据，第一行有两个正整数 N,M （ 1≤ N, M≤ 6 ），表示了数字矩阵为 N 行 M 列。 接下来 N 行，每行 M 个非负整数，描述了这个数字矩阵，满足 1 ≤ a_i,j≤ 10^5 。
输出共 T 行，每行一个非负整数，输出所求得的答案。
1 3 3 1 1 1 1 1 1 1 1 1
4
考点：dfs
数据规模 N ≤ 6 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出
推荐方向：dfs
一条路走到底再回溯，适合枚举全部方案与连通性判定。
思路框架（dfs 通法 · 非本题专属）
实现要点：回溯时务必把状态恢复干净；必要时加剪枝（可行性剪枝、最优性剪枝）。
复杂度：时间 O(状态数) ｜ 空间 O(递归深度)
该范式的通法易错点
对照本题
样例 1
1 / 3 3 / 1 1 1 / 1 1 1 / 1 1 14解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：华为机试编程模拟题1。