4565 - 取数游戏
时间限制 : 3 秒
内存限制 : 128 MB
一个NxM的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意两个数字不相邻(若一个数字在另外一个数字相邻的8个格子中的一个即认为这两个数字相邻)，求取出数字和最大是多少。
输入
第一行有两个正整数N和M(1≤N,M≤8)，表示数字矩阵为N行M列。
接下来N行，每行M个非负整数ai(1≤ai≤100)，描述了这个数字矩阵。
输出
一个整数，即所求得的答案。
样例
输入
4 4 67 75 63 10 29 29 92 14 21 68 71 56 8 67 91 25
输出
271
输入
2 3 87 70 85 10 3 17
输出
172
输入
3 3 1 1 1 1 99 1 1 1 1
输出
99
提示
[67] 75 63 10 29 29 [92] 14 [21] 68 71 56 8 67 [91] 25
来源
信友队